Leetcode | 第A节：数组综合题（1）

大家好！

熟悉我的人都知道，A就是10的意思。

在这一节我们开始更多关注数组和字符串的一些题目。事实上不仅仅是我们，官方也很难将这两个类别的题目，从算法或者数据结构的角度进行区分。毕竟很多很多的算法题都需要依赖数组，所有的字符串的题目不管用什么方法去做，它也都是字符串相关的问题。因此，我们在一开始介绍这些的时候，也会大概率与之前已经介绍的一些内容相结合。

那么我们开始吧。

数组类型的问题

请注意，对于想法特别直接的问题（例如模拟/枚举就可以解决的，单纯用来练习熟练度的，easy或medium-难度），是不会出现在我们的笔记中的。我们主要的目的还是抽象出一些数组问题中的解决问题的通法，用于攻克leetcode中相对比较困难的一些问题。

Problem 1: Leetcode 581 给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。 请你找出符合题意的 最短 子数组，并输出它的长度。

例如如果nums = [2,6,4,8,10,9,15]，那么输出就是5，因为中间的[6, 4, 8, 10, 9]进行升序排序，就可以得到正确的结果，并且这是最短的结果。

事实上对于这个问题，因为我们要找的是连续的子数组，所以容易想到直接排序，然后让排序后和排序前的结果相比较，看究竟改变了哪一个连续子数组。另外由于排序后的结果唯一，所以这里的“最短”其实是可以忽略的。

但是这一个题其实是有更好的解法的，相比较排序的

这个方法具有

的复杂度，我们来看看是怎么做到的。

注意这个问题，如果需要我们找到这个无序子数组，一定要需要确认这个数组的左边界和右边界。那么确认左边界的方法是什么呢？其实就是需要一个栈。具体来说，我们既然要确认左边界的位置，我们首先肯定要确认数组是升序的。那么只要是升序，我们可以把元素一直放入栈中，这些元素的位置一定是正确的。如果不再是升序了（也就是说，新放入的元素比栈顶元素要小，变成降序了），那么这个“新放入的元素”肯定就不是在正确的位置，那么它正确的位置，肯定是使得数组继续保持升序的。因此，可以一直弹出栈顶，一直到栈顶元素又比这个新元素要小就可以了。如果我们事先知道栈顶元素对应的下标为k，那么我们就知道了，新元素的正确位置下标一定是k+1。所以在入栈的时候，我们还是需要记录每一个元素在数组中的下标的。然后我们继续遍历数组，只要遇到降序的元素，我们就按照这个方式来确认它“正确”的位置，在这些位置中取一个最左的就可以了。当然，这样可以的原因也是在于，最小值一定会落在谷底，所以一定在降序寻找的时候可以找到它。

请注意，这个方法准确的原因在于题目中，已经事先假定了有一段连续的数组有问题，其他的数的顺序都没有问题。如果没有这个条件，那么即使是之前升序的数组，它们的位置也有可能是错误的，方法就失效了。

对于右边界，做法是类似的，只是这一次，我们要逆序遍历，并且把要求的“升序”改成降序。读者可以自己想一想为什么这样可以找到右边界。

好的，我们给出这个问题的核心代码。

public class Solution {
    public int findUnsortedSubarray(int[] nums) {
        Stack <Integer> stack = new Stack <Integer> ();
        int l = nums.length, r = 0;
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] > nums[i])
                l = Math.min(l, stack.pop());
            stack.push(i);
        }
        stack.clear();
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i])
                r = Math.max(r, stack.pop());
            stack.push(i);
        }
        return r - l > 0 ? r - l + 1 : 0;
    }
}

当然，这一个题其实可以有更巧的方法，也是利用了数组中的最小值和最大值决定左边界和右边界的特性。不过我们因为篇幅关系，这里就不再多说了，读者感兴趣可以自己参考题解。

关于栈，读者可以参考这一节

Leetcode | 第6节：栈与队列

Problem 2: Leetcode 41 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

比方说nums = [3,4,-1,1]，那么输出就是2。

这一个题是一道不太好想的题目，我们一步步来看，首先，我们只关心最小的正整数，所以负数可以不用管。这样的话，为了处理方便，我们直接把负数变成一个很大的正数即可。还需要注意的一点是，这一个题答案只有可能是

中的一个，因为数组长度为

，那么要不然就是

全有（这个时候答案是

），要不就是

中一定有一个数没有。

问题在于如何标记，如果要一个

的复杂度，必须有限次内遍历数组来得到结果。因此这里标记的点就在于数组的下标。具体来说，对于一个数

而言，如果它存在，那么我们就给下标为

的元素取一个相反数，让它变成负数。这样的话，遍历一遍，如果某一个数

变成了负数，就说明

是存在过的。否则就是不存在的。

因此最终，只需要再遍历一次数组，找哪一个元素还是正数即可。如果不存在，那么答案就是

。

好的，我们来看看核心代码吧。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int& num: nums) {
            if (num <= 0) {
                num = n + 1;
            }
        }
        for (int i = 0; i < n; ++i) {
            int num = abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -abs(nums[num - 1]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                return i + 1; // 注意返回的是下标+1
            }
        }
        return n + 1;
    }
};

这里我们用

标记的原因很简单，因为

和下标

碰巧差一个位移1。

Problem 3: Leetcode 845 我们把数组 A 中符合下列属性的任意连续子数组 B 称为 “山脉”： B.length >= 3 存在 0 < i < B.length - 1 使得 B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1] （注意：B 可以是 A 的任意子数组，包括整个数组 A。） 给出一个整数数组 A，返回最长 “山脉” 的长度。 如果不含有 “山脉” 则返回 0。

如果输入是[2,1,4,7,3,2,5]，那么输出就是5，因为山脉是[1,4,7,3,2]。

我们可以发现，对于一个山顶元素而言，它左边的元素一定是单调上升的，右边的元素一定是单调下降的。所以可以在数组的每一个位置去维护这样的一个状态，即“在这个位置，向左最远可以延伸的长度，和向右最远可以延伸的长度”。

对于位置

，我们用left[i]和right[i]分别表示左和右，那么很容易写出状态转移方程

right[i]的类似。我相信我不说大家也明白这个状态转移方程啥意思。而且大家其实可以发现，因为这是一个递推的关系，所以其实也只需要遍历一次数组，就可以拿到每一个位置的left[i]状态。然后再遍历就可以拿到right的值了。

那么最终，我们对于每个位置

，计算一下left[i]+right[i]+1即可。

好的，我们来看一下核心代码。

class Solution {
public:
    int longestMountain(vector<int>& arr) {
        int n = arr.size();
        if (!n) {
            return 0;
        }
        vector<int> left(n);
        for (int i = 1; i < n; ++i) {
            left[i] = (arr[i - 1] < arr[i] ? left[i - 1] + 1 : 0);
        }
        vector<int> right(n);
        for (int i = n - 2; i >= 0; --i) {
            right[i] = (arr[i + 1] < arr[i] ? right[i + 1] + 1 : 0);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (left[i] > 0 && right[i] > 0) {
                ans = max(ans, left[i] + right[i] + 1);
            }
        }
        return ans;
    }
};

Problem 4: Leetcode 42 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

例如输入是height = [0,1,0,2,1,0,1,3,2,1,2,1]，那么输出就是6，这个height对应的图如下：

这是一道极为经典的动态规划的问题（面试也很喜欢考察），总体的思路上也和Problem 3很类似。

这里其实是想观察，在某一个位置上可以达到的雨水的最高高度。那么它很明显受制于三个因素：左边的柱子高度，右边的柱子高度，和当前位置的高度。那么在这里，注意，左边的柱子高度，其实就是从这个位置出发，往左走，可以找到的最高的柱子高度。因此如果我们设left, right数组表示左右的话，状态转移方程就是

right数组类似。height[i]表示

这个位置，柱子的高度。

有了这两个数据之后，大家可以看出，最后水的高度就是min(left[i], right[i]) - height[i]。毕竟短板就会漏水嘛。

所以综合来看，我们只是利用动态规划做了两个状态，然后再通过遍历找到了每一个位置的水的高度就可以了。

关于动态规划的其他题目，可以看看这两节。

Leetcode | 第一节：动态规划（上）

Leetcode | 第2节：动态规划（下）

我们在之后的综合题中还会经常提到动态规划的问题。

好的，我们来看看核心代码。

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if (n == 0) {
            return 0;
        }
        vector<int> leftMax(n);
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i) {
            leftMax[i] = max(leftMax[i - 1], height[i]);
        }

        vector<int> rightMax(n);
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = max(rightMax[i + 1], height[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
};

Problem 5: Leetcode 84 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。

比方说如果输入是heights = [2,1,5,6,2,3]，那么输出就是10。具体可以看下图

对于这个问题，和Problem 3和4比较类似，本质上我们需要找到两根柱子，然后其宽度就是柱子所跨过的宽度，高度就是这中间经过的所有柱子中，高度最小的那一根。所以有一种寻找合理的答案的方案就是，我们先确认每一根柱子的高度，然后以某一根柱子作为基线（不妨设高度为

），然后向左向右拓展，一直找到小于其高度的柱子。这样的话，左右拓展所经过的柱子，高度都是

的，在这个情况下，就可以认为围起来的这个矩形的高度是

，而宽度就是向左向右拓展可以达到的宽度。

所以问题其实很简单，就是固定高度，然后向左向右延伸，去看究竟可以延伸到什么程度。那么如何知道它向左延伸的位置呢？这里可以思考这么一个问题，就是，固定一个位置

，向左枚举到了一个位置

，那么如果height[i] >= height[j]，这个时候

就不是这个可以到达的最远位置。所以其实是要找到最远的满足height[i] < height[j]的位置。所以事实上，我们可以发现，我们每一次希望找到的“最远位置”，一定在height上和index上都是升序排列的，这就可以使用单调栈来解决问题。

具体来说，我们可以把柱子的高度都拉出来放到一个数组内，然后维护一个栈，每放入一个新的数字之前，都检查一下栈顶元素是否小于这个新元素。小于的话就直接放进去，否则的话就要一直出栈，到条件满足为止。到条件满足的时候，记录栈顶元素的位置，这个位置就是这个新元素左边可以到达的最远距离。可以看出来，这个“不断出栈”的过程，其实就是柱子向左枚举，寻找高度比它小的柱子的过程。

但是如果一开始栈是空的，那么新元素就可以直接放入栈顶，这个时候相当于它所在位置的左边所有的柱子都比它高，那么就需要单独处理，最远的位置我们可以记为一个不存在的值（例如

），然后用额外的判断条件计算即可。

那么右边界呢？其实只需要反过来遍历一遍即可，并且依然目的是寻找一个升序排列。读者可以自己思考一下为什么。

单调栈的相关问题的解决思想，可以参考这一节。

Leetcode | 第6节：栈与队列

好的，我们来看一下核心代码吧。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> left(n), right(n);
        
        stack<int> mono_stack;
        for (int i = 0; i < n; ++i) {
            while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
                mono_stack.pop();
            }
            left[i] = (mono_stack.empty() ? -1 : mono_stack.top());
            mono_stack.push(i);
        }

        mono_stack = stack<int>();
        for (int i = n - 1; i >= 0; --i) {
            while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
                mono_stack.pop();
            }
            right[i] = (mono_stack.empty() ? n : mono_stack.top());
            mono_stack.push(i);
        }
        
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }
};

我相信不用再解释，这个right[i] - left[i] - 1为什么是宽度了，对吧？

Problem 6: Leetcode 85 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

比方说如果matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]，那么输出就是6。具体这个矩形的样子可以看下图。

这一个题其实是从Problem 5（Leetcode 84）发源过来的，所以我们也顺便讲一下这一个题。

对于这个问题，其实也可以幻化成之前的题提到的柱状图的求解思路。也就是说，我们可以针对某一行的某一个元素，考虑以它为右下角节点的矩形，先看它左边有多少个

，然后再枚举高度。这样形成的矩形的宽度，就是这个点所经过高度上，左边

个数的最小值。高度就是你枚举的高度。

这么说怪抽象的，画个图吧。

在这里，四个颜色分别代表了枚举的四个高度。每一个数字分别代表这一个位置左边的

的个数。读者可以看出根据这个规则，枚举的四个高度分别对应的宽度为3, 3, 2, 1。

因此解题的核心思路其实和上一题是一模一样的，差别仅仅落在了枚举的位置和方式上。具体来说，我们可以枚举每一列，根据每一列的左边的1的个数，来设置“高度”，而宽度也就是列所可以延伸的长度。这个具体也可以画一张图。

红色和蓝色对应的是选择不同列所画出的不同的柱状图。我们也在每一行分别标出了这里的“柱子”的高度（对应上一题来看）。

所以可以看出来，如果说矩阵有

列，那么这一个问题就相当于跑了

次的单调栈，也就是跑了

次的上一题。

好的，那么我们来看一下核心代码吧。

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if (m == 0) {
            return 0;
        }
        int n = matrix[0].size();
        vector<vector<int>> left(m, vector<int>(n, 0));

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    left[i][j] = (j == 0 ? 0: left[i][j - 1]) + 1;
                }
            }
        }

        int ret = 0;
        for (int j = 0; j < n; j++) { // 对于每一列，使用基于柱状图的方法
            vector<int> up(m, 0), down(m, 0);

            stack<int> stk;
            for (int i = 0; i < m; i++) {
                while (!stk.empty() && left[stk.top()][j] >= left[i][j]) {
                    stk.pop();
                }
                up[i] = stk.empty() ? -1 : stk.top();
                stk.push(i);
            }
            stk = stack<int>();
            for (int i = m - 1; i >= 0; i--) {
                while (!stk.empty() && left[stk.top()][j] >= left[i][j]) {
                    stk.pop();
                }
                down[i] = stk.empty() ? m : stk.top();
                stk.push(i);
            }

            for (int i = 0; i < m; i++) {
                int height = down[i] - up[i] - 1;
                int area = height * left[i][j];
                ret = max(ret, area);
            }
        }
        return ret;
    }
};

Problem 7: Leetcode 334 给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。 如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。

这一个问题虽然明面上是一道medium，不过解决它的思路还是很巧妙的。考虑到它是一道高频题，我们这里简单说一下它的这个巧妙的解题方法。

首先这个题要找到3个，可能一下子不太好想。但是我们可以找到2个的，记为small和mid，并且保证前后顺序（例如，可以设置为第一个和第二个，如果可以的话）。然后这第三个数字怎么找呢？

这里的想法是这样的，对于数组中每一个数我们都枚举一下，观察它与small和mid的大小关系。如果比small小，就替换small，否则如果比mid小，就替换mid，否则就相当于比它们俩都大了，那就说明找到了。

这里有一个问题就是，为什么这样就一定可以找到呢？现在我们假设已经找到了small和mid。然后我们发现了一个更小的元素，替换了small。那么这个时候，虽然这个small和mid的下标不是一个严格递增的顺序，但是大家可以发现，这个时候其实依然会有一个值，它大于当前的small（它是之前的small），小于mid。所以这个判断标准依然是合适的。但是如果mid改变了，那么因为我们数组是从前往后遍历的，所以这个新的mid的位置一定在新的small的后面，所以这个下标又重新变成了递增的顺序，这样逻辑就合理了。

具体的变法我们画一张图。

这里的带'的元素表示变换之后的元素。打勾说明存在，而且可以看出来，无论怎么检查，我们都能够说明存在性，因此答案是不会被影响的。

好的，接下来我们来看看，代码应该怎么写吧。

class Solution {
public:
  bool increasingTriplet(vector<int>& nums) {
    int len = nums.size();
    if (len < 3) return false;
    int small = INT_MAX, mid = INT_MAX;
    for (auto num : nums) {
      if (num <= small) {
        small = num;
      } else if (num <= mid) {
        mid = num;
      } 
      else if (num > mid) {
        return true;
      }
    }
    return false;    
  }
};

读者可以自己思考一下，为什么这个方法一定不会漏掉数组中，满足条件的三元组。事实上使用反证法就可以看出来，证明也不是太困难。

Problem 8: Leetcode 128 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

例如说输入是nums = [100,4,200,1,3,2]，那么输出就是4，这个时候连续序列是[1, 2, 3, 4]，注意我们不需要它们是连续的。

对于这一个问题，大家第一个容易想到的其实是哈希表。这样的话可以非常快的去查找出，是否存在连续的，像

一样的数列。但是很明显，我们不可能对每一个元素

，都去查一遍

是否也在哈希表中的，因为在这种情况下，很容易发生重复运算。就像如果你已经查出了

是一个连续的序列，那么就没有必要再去对

，去查是否存在

了，这个长度不可能有之前的长度要大的。

为了避免这种情况，一个方法就是在枚举数组的时候，先检查这个数

之前的一个，也就是

是否已经存在于数组中了。判断完之后，再去看是否有连续的数列。这样就不会有重复的可能了。

另外这里其实重复元素也是没有什么用的，所以去重也是需要考虑的一环。

好的，我们来看一下核心代码吧。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> num_set; // 哈希表，注意这里已经有了去重
        for (const int& num : nums) {
            num_set.insert(num);
        }

        int longestStreak = 0;

        for (const int& num : num_set) {
            if (!num_set.count(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (num_set.count(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = max(longestStreak, currentStreak);
            }
        }

        return longestStreak;           
    }
};

Problem 9: Leetcode 152 给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

比方说输入是[2,3,-2,4]，那么输出就是6，对应的子数组就是[2, 3]。

这一个问题其实很容易看出来是一个动态规划的问题，根据最长上升子序列的经验，其实可以考虑有这么一个状态转移方程。

即考虑以最后一个元素为结束的连续子序列。但是这里存在一个反例是，考虑数组a = [5, 6, -3, 4, -3]，那么会发现，其实最大值对应了数组所有元素都相乘在一起的情况。但是如果按照这个转移方程，那么你会发现我们没有办法得到这个结果，因为枚举到最后一个-3的时候，我们得到的状态是从倒数第二个位置过来的，而倒数第二个位置的“最大值”其实是4，所以我们最后一个-3其实相当于只能从4 * -3与-3中挑选一个。换句话说，这里的当前位置的最优解，并没有办法通过上一个最优解转移过来，因此这个方程是失效的。

怎么办呢？这里有一个想法。可以看出，我们会遇到负数的影响，而且正确的情况是，如果这一个点是负数，那么之前的状态也应该是一个负数，这样相乘起来才能得到一个尽可能大的数。出于这个思考，我们考虑把状态转移方程写成这样

也就是说不仅仅维护一个最大值的状态，也维护一个最小值的。最小值的就是为了应对当前点是负数的情况。

写到这里，代码就比较明确了。

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        vector <int> maxF(nums), minF(nums);
        for (int i = 1; i < nums.size(); ++i) {
            maxF[i] = max(maxF[i - 1] * nums[i], max(nums[i], minF[i - 1] * nums[i]));
            minF[i] = min(minF[i - 1] * nums[i], min(nums[i], maxF[i - 1] * nums[i]));
        }
        return *max_element(maxF.begin(), maxF.end());
    }
};

最终还是返回最大值数组maxF中里面的最大元素即可。

当然了，这一题也完全可以进一步优化，即使用滚动数组的思路。具体的我们留给读者思考。

小结

本节虽然我们只放了9道题，但是要明白，数组的题目非常多而杂，而且常见的解数组题相关的一些技巧我们都没有在这一节提到，因此还会有很多题目在后面等着大家。

下一节我们会介绍一些前缀和，双指针，滑动窗口等方法所应用的题目。同样，我们也会说一些需要用到之前提到的算法的题目。