跳转至

单调栈

始终满足单调性的栈。新元素入栈时，先把比它大（小）的元素都出栈，自己再入栈，以维持单调性。

典型的应用场景：在一维数组中，寻找每个元素左（右）边第一个满足某条件的元素，栈中存的是还没找到的元素的下标。

每日温度

739. 每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

提示：

  • 1 <= temperatures.length <= 105
  • 30 <= temperatures[i] <= 100

算是模板题了。

解析

单调栈中存的是当前还没处理的元素下标。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> ans(temperatures.size(), 0);
        stack<int> s;

        for (int i = 0;i < temperatures.size();i++)
        {
            while (s.size() && temperatures[i] > temperatures[s.top()])
            {
                ans[s.top()] = i - s.top();
                s.pop();
            }
            s.push(i);
        }

        return ans;
    }
};

时间复杂度：\(O(n)\)。每个元素下标最多入栈一次，出栈一次。

空间复杂度：\(O(n)\)。

下一个更大元素 I

496. 下一个更大元素 I

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

提示：

  • 1 <= nums1.length <= nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 104
  • nums1和nums2中所有整数 互不相同
  • nums1 中的所有整数同样出现在 nums2 中

解析

nums1 中数字不是按顺序排的。不过没什么难度，加个 map 就行。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> ids;
        for (int i = 0;i < nums1.size();i++)
        {
            ids[nums1[i]] = i;
        }

        vector<int> ans(nums1.size(), -1);
        stack<int> s;

        for (int i = 0;i < nums2.size();i++)
        {
            while (s.size() && nums2[i] > nums2[s.top()])
            {
                if (ids.count(nums2[s.top()]))
                {
                    ans[ids[nums2[s.top()]]] = nums2[i];
                }
                s.pop();
            }
            s.push(i);
        }

        return ans;
    }
};

时间复杂度：\(O(m+n)\)。

空间复杂度：\(O(m+n)\)。

下一个更大元素 II

503. 下一个更大元素 II

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

提示:

  • 1 <= nums.length <= 104
  • -109 <= nums[i] <= 109

解析

遍历两次数组就行。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> ans(nums.size(), -1);
        stack<int> s;

        for (int i = 0;i < 2 * nums.size();i++)
        {
            int idx = i % nums.size();
            while (s.size() && nums[idx] > nums[s.top()])
            {
                ans[s.top()] = nums[idx];
                s.pop();
            }
            s.push(idx);
        }

        return ans;
    }
};

时间复杂度：\(O(n)\)。

空间复杂度：\(O(n)\)。

接雨水

42. 接雨水

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

提示：

  • n == height.length
  • 1 <= n <= 2 * 104
  • 0 <= height[i] <= 105

经典题，非常重要。

解析 1

动态规划。

对下标 i 这一列，能接的雨水数量为 max(height[:i+1]) 和 max(height[i:]) 的最小值减去 height[i]。

用 leftMax[i] 表示 max(height[:i+1])，rightMax[i] 表示 max(height[i:])。有

  • leftMax[0] = height[0]
  • leftMax[i] = max(leftMax[i-1], height[i])
  • rightMax[n-1] = height[n-1]
  • rightMax[i] = max(rightMax[i+1], height[i])
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int trap(vector<int>& height) {
        vector<int> leftMax(height.size());
        leftMax[0] = height.front();

        for (int i = 1; i < height.size(); i++)
        {
            leftMax[i] = max(leftMax[i - 1], height[i]);
        }

        vector<int> rightMax(height.size());
        rightMax.back() = height.back();

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

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

时间复杂度：\(O(n)\)。

空间复杂度：\(O(n)\)。

解析 2

双指针。

动态规划中，leftMax[i] 只和前一项以及 height[i] 有关，rightMax[i] 只和后一项以及 height[i] 有关，所以可以想办法把数组优化掉。

改成双指针后，令

  • leftMax = max(height[:left+1])
  • rightMax = max(height[right:])

同时，让 left 或 right 始终停留在最高的柱子处，即满足

1
max(height[left], height[right]) == max(leftMax, rightMax)

这样的话，可得几条推论：

  • leftMaxInDP[i] >= height[j]，对任意 j <= i 都成立
  • rightMaxInDP[i] >= height[j]，对任意 j >= i 都成立
  • leftMax == leftMaxInDP[left]
  • rightMax == rightMaxInDP[right]
  • leftMax <= max(height[left], height[right])
  • rightMax <= max(height[left], height[right])

如果 height[left] < height[right]，则必有

1
leftMaxInDP[left] == leftMax <= height[right] <= rightMaxInDP[left]

根据动态规划中，第 i 列能接的雨水数量公式

1
min(leftMaxInDP[i], rightMaxInDP[i]) - height[i]

可得，第 left 列能接的雨水数量为 leftMax - height[left]。然后，因为 left 列比 right 列矮，所以向右移动 left。

如果 height[left] >= height[right]，同样的，有

1
rightMaxInDP[right] == rightMax <= height[left] <= leftMaxInDP[right]

可得，第 right 列能接的雨水数量为 rightMax - height[right]。然后，因为 right 列比 left 列矮，所以向左移动 right。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int trap(vector<int>& height) {
        int leftMax = -1;
        int rightMax = -1;
        int left = 0;
        int right = height.size() - 1;
        int ans = 0;

        // 最后 left 和 right 一定会聚在最高处，这地方肯定接不了雨水
        // 这里条件中等号可以加也可以不加
        while (left < right)
        {
            leftMax = max(leftMax, height[left]);
            rightMax = max(rightMax, height[right]);

            if (height[left] < height[right])
            {
                ans += leftMax - height[left];
                left++;
            }
            else
            {
                ans += rightMax - height[right];
                right--;
            }
        }

        return ans;
    }
};

时间复杂度：\(O(n)\)。

空间复杂度：\(O(1)\)。

解析 3

单调栈。前两种方法是竖着数雨水，而单调栈是横着数雨水。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        stack<int> s;

        for (int i = 0;i < height.size();i++)
        {
            while (s.size() && height[i] > height[s.top()])
            {
                int mid = s.top();
                s.pop();

                if (s.size())
                {
                    int left = s.top();
                    int w = i - left - 1;
                    int h = min(height[left], height[i]) - height[mid];
                    ans += w * h;
                }
            }
            s.push(i);
        }

        return ans;
    }
};

时间复杂度：\(O(n)\)。

空间复杂度：\(O(n)\)。

柱状图中最大的矩形

84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

提示：

  • 1 <= heights.length <=105
  • 0 <= heights[i] <= 104

解析

对于第 i 列的柱子，将它向左右扩展到最远，得到一个可能的矩形。遍历所有这样的矩形，取最大值。

向左右扩展到最远，换种角度想，即找到左边和右边第一个比自己矮的柱子。典型的单调栈应用。

维护一个从栈底到栈顶递增的单调栈，对于栈中的某个柱子，它下面的那个元素就是它左边第一个比自己矮的柱子。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int ans = 0;
        stack<int> s;

        // 在前后插入哨兵，保证单调栈中所有柱子都能被处理
        heights.insert(heights.begin(), 0);
        heights.push_back(0);

        for (int i = 0;i < heights.size();i++)
        {
            while (s.size() && heights[i] < heights[s.top()])
            {
                int mid = s.top();
                s.pop();

                if (s.size())
                {
                    int w = i - s.top() - 1;
                    int h = heights[mid];
                    ans = max(ans, w * h);
                }
            }
            s.push(i);
        }

        return ans;
    }
};

时间复杂度：\(O(n)\)。

空间复杂度：\(O(n)\)。