Medium

题目描述

给定一个整数数组 nums。

你必须重复执行以下合并操作，直到无法进行更多更改：

  • 如果任意两个相邻元素相等，选择当前数组中最左边的这样的相邻对，并用等于它们和的单个元素替换它们。

每次合并操作后，数组大小减少 1。在更新的数组上重复此过程，直到无法进行更多更改。

返回所有可能的合并操作后的最终数组。

示例 1：

输入：nums = [3,1,1,2]
输出：[3,4]
解释：
- 中间两个元素相等，合并为 1 + 1 = 2，得到 [3, 2, 2]。
- 最后两个元素相等，合并为 2 + 2 = 4，得到 [3, 4]。
- 没有相邻相等元素剩余。因此，答案是 [3, 4]。

示例 2：

输入：nums = [2,2,4]
输出：[8]
解释：
- 前两个元素相等，合并为 2 + 2 = 4，得到 [4, 4]。
- 前两个元素相等，合并为 4 + 4 = 8，得到 [8]。

示例 3：

输入：nums = [3,7,5]
输出：[3,7,5]
解释：
数组中没有相邻相等元素，所以不执行任何操作。

约束条件：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

解题思路

这道题可以使用栈的思想来解决，通过模拟合并过程。

核心思路： 从左到右遍历数组，使用栈来维护当前的结果。对于每个元素：

  1. 如果栈为空或栈顶元素与当前元素不相等，直接入栈
  2. 如果栈顶元素与当前元素相等，弹出栈顶元素，将两者之和作为新元素继续处理

关键点：

  • 合并后的新元素可能会与栈中前面的元素再次相等，所以需要用循环继续检查
  • 由于合并可能产生较大的数值，需要使用 long long 类型避免溢出
  • 题目要求选择"最左边"的相邻相等对，我们的从左到右处理天然满足这个要求

算法步骤：

  1. 初始化栈
  2. 遍历数组中的每个元素
  3. 对于当前元素，持续检查是否能与栈顶合并
  4. 如果能合并，弹出栈顶并更新当前元素为两者之和，继续检查
  5. 如果不能合并，将当前元素入栈
  6. 返回栈中的所有元素

这种方法确保了每次都是处理最左边的相邻相等对，并且能够处理连续的合并操作。

代码实现

class Solution {
public:
    vector<long long> mergeAdjacent(vector<int>& nums) {
        vector<long long> stack;
        
        for (int num : nums) {
            long long current = num;
            
            while (!stack.empty() && stack.back() == current) {
                current += stack.back();
                stack.pop_back();
            }
            
            stack.push_back(current);
        }
        
        return stack;
    }
};

class Solution:
    def mergeAdjacent(self, nums: List[int]) -> List[int]:
        stack = []
        
        for num in nums:
            current = num
            
            while stack and stack[-1] == current:
                current += stack.pop()
            
            stack.append(current)
        
        return stack

public class Solution {
    public IList<long> MergeAdjacent(int[] nums) {
        List<long> stack = new List<long>();
        
        foreach (int num in nums) {
            long current = num;
            
            while (stack.Count > 0 && stack[stack.Count - 1] == current) {
                current += stack[stack.Count - 1];
                stack.RemoveAt(stack.Count - 1);
            }
            
            stack.Add(current);
        }
        
        return stack;
    }
}

var mergeAdjacent = function(nums) {
    const stack = [];
    
    for (const num of nums) {
        let current = num;
        
        while (stack.length > 0 && stack[stack.length - 1]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型时间复杂度空间复杂度
时间复杂度O(n)-
空间复杂度-O(n)

详细分析：

  • 时间复杂度： O(n)，其中 n 是数组长度。虽然内层有 while 循环，但每个元素最多被处理常数次（入栈一次，可能被合并弹出一次），总体仍是线性时间。
  • 空间复杂度： O(n)，在最坏情况下（没有相邻相等元素），栈中需要存储所有 n 个元素。