【代码随想录】单调栈

发表于 2024-02-29 更新于 2024-04-20 分类于代码随想录阅读次数：本文字数： 5k 阅读时长 ≈ 17 分钟

单调栈

每日温度

题目：739

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

分析：

寻找后面第一个比自己高的值所在的位置.

思路1：暴力破解，外层循环遍历每一个元素，内层循环从当前元素向后遍历，寻找第一个比当前值大的元素所在位置，如果后面没有比当前值大的元素或者只有与当前值相等的元素，那么就填充0.

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> result(temperatures.size(), 0); // 初始化下一个比当前值高在0天后
        int len = temperatures.size();
        for (int i = 0; i < len; i++) {
            // 当前日期温度
            int cur = temperatures[i];
            // 向后尝试寻找更高的温度
            for (int j = i + 1; j < len; j++) {
                // 如果出现更高温度则计算在几天后
                if (temperatures[j] > cur) {
                    result[i] = j - i;
                    break; // 只记录第一次出现更高温度的位置
                }
            } // end inner for
        } // end outer for

        return result;
    }
};

时间复杂度O(n^2)；空间复杂度O(n)

超出时间限制

思路2：（单调栈）

怎么能想到用单调栈呢？什么时候用单调栈呢？

通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。时间复杂度为O(n)。

例如本题其实就是找找到一个元素右边第一个比自己大的元素，此时就应该想到用单调栈了。

单调栈中存放的是什么：
本题中由于求的是位置，因此应该存放下标
单调栈中的元素是递增还是递减？
在本题中从栈顶到栈底应该是递增的。因为只有当栈顶元素是栈中最小的元素时，从右边增加新的元素时，才能判断第一个比栈顶元素大的元素是谁。
即：如果求一个元素右边第一个更大元素，单调栈（从栈顶到栈底）就是递增的，如果求一个元素右边第一个更小元素，单调栈就是递减的。
使用单调栈主要有三个判断条件。
- 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况：此时应该入栈
- 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况：由于求的是比栈顶元素更大而非相等的元素，因此应该入栈
- 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况：此时出现第一个比栈顶元素大的元素，应该计算位置并将栈顶元素出栈

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int len = temperatures.size();
        stack<int> st; // 单调栈，从栈顶到栈底递增，存放下标
        vector<int> result(len, 0); // 初始化为0
        if (len == 0) return result; // 下面的代码要求至少一个元素
        
        // 第一个元素入栈
        st.push(0);

        for (int i = 1; i < len; i++) {
            int cur = temperatures[i]; // 当前值
            if (cur <= temperatures[st.top()]) {
                st.push(i);
            } else {
                // 栈顶元素大于当前元素时
                // 一直出栈直到小于或者等于
                while (!st.empty() && cur > temperatures[st.top()]) {
                    result[st.top()] = i - st.top(); // 计算当前值与之前值的距离
                    st.pop();
                }
                st.push(i); // 当前值的位置入栈
            }
        }

        return result;
    }   
};

时间复杂度O(n)；空间复杂度O(n)

下一个更大元素 I

题目：496

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] 是如上所述的 下一个更大元素 。

分析：

对于nums1中每个元素，首先需要在nums2中找到对应的位置

然后在nums2中找到比当前位置元素更大的元素。

思路1：外层循环遍历每一个nums1中的元素，然后在内循环中：首先需要遍历nums2找到对应下标；然后再找到第一个比当前位置大的位置。总的时间复杂度为O(n^2)。

思路2：上述思路的瓶颈在于：每次循环都需要重新遍历nums2，这些操作是重复的。

这里找下一个最大值是在nums2上操作，所以使用单调栈应该遍历nums2。那么就需要将元素在nums1中下标使用hash表保存起来（值，下标），方便更新结果数组。

使用单调栈：

1.栈中元素是什么：栈中是每个元素在nums2中的下标

2.栈的顺序是：从栈顶到栈底递增。这样当遇到下一个比栈顶元素更大的值时才能知道

3.三种情况：（1）当栈顶元素大于新元素时：新元素入栈

（2）当栈顶元素等于新元素时：由于是找更大的元素，所以新元素仍然入栈

（3）当栈顶元素小于新元素时：此时就找到了下一个更大的元素，应该出栈，计算相对位置；然后将新元素入栈，新元素入栈必须是最小的，所以需要不断出栈元素知道新元素大于等于栈顶元素。

单调栈中维护的是还没有找到下一个更大的元素们，同时又保证了相对位置。当找到下一个更大元素就会出栈。

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> map; // 记录nums1中值与下标的映射
        int nums1_size = nums1.size();
        for (int i = 0; i < nums1_size; i++)
            map[nums1[i]] = i;
        
        stack<int> st; // 单调栈，保存nums2中每个元素下标，从栈顶到栈底递增
        vector<int> result(nums1_size, -1); // 初始化为-1
        int nums2_size = nums2.size();
        if (nums2_size == 0) exit(-1); // 下面的代码要求nums2至少一个元素
        st.push(0); // 入栈一个元素

        // 遍历nums2
        for (int i = 1; i < nums2_size; i++) {
            int cur = nums2[i]; // 当前值
            if (nums2[st.top()] >= cur) {
                // 如果栈顶下标对应的值大于当前元素
                st.push(i);
            } else {
                // 如果新元素比较大
                while (!st.empty() && nums2[st.top()] < cur) {
                    // 首先判断栈顶元素是否存在于nums1中
                    if (map.find(nums2[st.top()]) != map.end()) {
                        // 保存下一个更大元素的值
                        int nums1_index = map[nums2[st.top()]]; // 在nums1中的下标
                        result[nums1_index] = cur;
                    }
                    st.pop();
                }
                // 新元素下标入栈
                st.push(i);
            }
        }

        return result;
    }
};

时间复杂度O(n)；空间复杂度O(n)

PS：1.结果数组中应该保存的是下一个更大元素的值，而不是相对位置；2.如果想要访问hash表，应该先判断值是否在hash表中。nums1是nums2的子集，所以nums2中可能存在nums1中不存在的值；3.可以构建（nums1中的值，下标）是因为无重复元素。

下一个更大元素 II

题目：503

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

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

分析：

如果处理循环数组：如果一个元素的后面存在更大的值，那么遍历一次数组就能完成；但是如果更大的值在前面，这里是循环数组，所以需要遇到末尾从头开始遍历。

思路1：将两个数组拼接，使用单调栈计算出每一个元素的下一个最大值，最后再把结果集即result数组resize到原数组大小就可以了。

思路2：不扩充nums，而是在遍历的过程中模拟走了两边nums。即在获取下标时进行取余操作

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int nums_size = nums.size();
        vector<int> result(nums_size, -1); // 初始化结果数组为-1

        if (nums_size == 0) return result; // 下面的代码要求至少一个元素
        
        stack<int> st; // 单调栈，栈中存放元素下标，范围是[0, nums_size)
        st.push(0); // 存放第一个元素的下标

        // 模拟遍历两次数组
        // 递增范围是[0, 2 * nums_size)
        // 第二遍遍历时实际的下标应该是i % nums_size
        for (int i = 1; i < nums_size * 2; i++) {
            int cur = nums[i % nums_size]; // 当前值
            if (nums[st.top()] >= cur) {
                // 如果栈顶元素更大
                st.push(i % nums_size);
            } else {
                // 如果栈顶元素遇到更大的元素
                while (!st.empty() && nums[st.top()] < cur) {
                    // 保存更大的值作为答案
                    result[st.top()] = cur;
                    st.pop();
                }
                st.push(i % nums_size);
            }
        }

        return result;
    }
};

时间复杂度O(n)；空间复杂度O(n)

接雨水

题目：42

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

示例1：

1
2
3

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

分析：

思路1：暴力破解法：按照每一列求当前列能够装的雨水体积。

例如求第四列的雨水体积，

列4 左侧最高的柱子是列3，高度为2（以下用lHeight表示）。

列4 右侧最高的柱子是列7，高度为3（以下用rHeight表示）。

列4 柱子的高度为1（以下用height表示）

那么列4的雨水高度为列3和列7的高度最小值减列4高度，即： min(lHeight, rHeight) - height。

列4的雨水高度求出来了，宽度为1，相乘就是列4的雨水体积了。如果当前位置高于两侧，那么高度值是负数，此时不计入体积。

按照以上方法遍历除了第一列和最后一列，求出每一列的雨水数目，即可获得总的雨水数。

class Solution {
public:
    int trap(vector<int>& height) {
        int len = height.size(); // 列数
        int result = 0;

        // 遍历除了第一列和最后一列
        // 求每一列能够装的雨水数
        for (int i = 1; i < len - 1; i++) {
            // 当前列位置高度
            int cur_h = height[i];
            int left_h, right_h; // 左右最高值
            left_h = right_h = cur_h;

            // 求出左侧最高位置
            for (int left = i - 1; left >= 0; left--) {
                if (height[left] > left_h) left_h = height[left];
            }
            // 求出右侧最高位置
            for (int right = i + 1; right < len; right++) {
                if (height[right] > right_h) right_h = height[right];
            }

            // 计算当前位置能够装的雨水数目
            int vol = min(left_h, right_h) - cur_h;
            if (vol > 0) result += vol; // 如果两侧位置高于当前位置体积才会大于0
        }

        return result;
    }
};

时间复杂度O(n^2)，在遍历数组中分别向左和向右再次遍历数组；空间复杂度O(1)

思路2：上面的算法的瓶颈在于：每次循环中找左和右的最大值时，都是从当前位置向两边遍历，这里是存在重复操作的。

这里可以先遍历数组，找到每个位置左边的最大值和右边的最大值，这样再遍历每一列计算。

class Solution {
public:
    int trap(vector<int>& height) {
        int len = height.size(); // 列数
        vector<int> left_h(len, 0); // 每个位置左边最大值
        vector<int> right_h(len, 0); // 每个位置右边最大值
        // 求每个位置左边最大值
        left_h[0] = height[0];
        for (int i = 1; i < len; i++) 
            left_h[i] = max(left_h[i - 1], height[i]);
        
        // 求每个位置右边最大值
        right_h[len - 1] = height[len - 1];
        for (int i = len - 2; i >= 0; i--)
            right_h[i] = max(right_h[i + 1], height[i]);
        
        // 遍历除了第一列和最后一列求当前位置雨水数
        int result = 0;
        for (int i = 1; i < len; i++) {
            int vol = min(left_h[i], right_h[i]) - height[i];
            if (vol > 0) result += vol;
        }

        return result;
    }
};

时间复杂度O(n)；空间复杂度O(n)

思路3：单调栈：单调栈就是保持栈内元素有序。和栈与队列：单调队列 (239. 滑动窗口最大值)一样，需要我们自己维持顺序，没有现成的容器可以用。

通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。

使用单调栈记录每一个位置的高度，栈中的顺序应该是从栈顶到栈底递增，这样当遇到下一个更高的位置时，栈顶第二个元素和新元素都比栈顶元素高，这样形成凹槽可以存放雨水。

1.栈中存放什么：每个高度的下标

2.栈中顺序：从栈顶到栈底递增

3.三种情况：（1）当栈顶元素大于新元素时，新元素入栈；

（2）当栈顶元素等于新元素时，栈顶元素出栈，新元素入栈；

（3）当栈顶元素小于新元素时，以min(栈顶第二个元素，新元素) - 栈顶元素为高度，以（新元素下标 - 栈顶第二个元素下标） - 1为宽度计算雨水体积。

class Solution {
public:
    int trap(vector<int>& height) {
        int len = height.size();
        int result = 0; 
        
        if (len == 0) return 0; // 下面代码要求至少一个元素

        stack<int> st; // 存放每个高度的下标，从栈顶到栈底递增
        st.push(0); // 第一个高度下标入栈

        for (int i = 1; i < len; i++) {
            // 当前位置高度
            int cur = height[i];
            if (height[st.top()] > cur) {
                // 如果栈顶元素大
                st.push(i);
            } else if (height[st.top()] == cur) {
                st.pop();
                st.push(i);
            } else {
                // 栈顶元素小于新元素
                // 由（栈顶第二元素，新元素）组成两边
                // 由栈顶元素作为底部
                while (!st.empty() && height[st.top()] < cur) {
                    int mid = height[st.top()]; // 栈顶元素作为中间的底部
                    st.pop();
                    // 尝试获取栈顶第二元素
                    if (!st.empty()) {
                        int h = min(height[st.top()], cur) - mid; // 以较小的高度作为边
                        int w = i - st.top() - 1;
                        result += h * w;
                    }
                }

                st.push(i); // 新元素入栈
            }
        } // end for

        return result;
    }
};

时间复杂度O(n)；空间复杂度O(n)

柱状图中最大的矩形

题目：84

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

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

示例1：

1
2
3

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

分析：

遍历每个柱子，以当前柱子高度作为高的最大矩形。那么就需要分别向左和向右找到第一个小于当前高度的位置。

与上一题一样，如果在外层遍历每个柱子的循环中分别向左和向右寻找比当前位置更小的位置，那么时间复杂度为O(n^2)。

当我们找 i 左边第一个小于 heights[i] ，如果 heights[i-1] >= heights[i] ，其实就是和 heights[i-1] 左边第一个小于 heights[i-1] 一样。依次类推，右边同理。

所以考虑使用一个数组，数组记录每个柱子左边第一个小于该柱子的下标。

与上一题不同的是，上一题是求左边最大值和右边最大值。本题是求左边第一个更小的值和右边第一个更小的所在的位置。

所以本题在求这个数组的难度上更高。

求出数组之后就遍历每个柱子，然后以当前柱子高度为高，以右边界-左边界-1作为宽计算矩形面积。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int len = heights.size();
        // 求每个位置左边第一个更小元素的下标
        vector<int> min_left_index(len);
        min_left_index[0] = -1; // 第一个元素左边没有更小的元素
        for (int i = 1; i < len; i++) {
            int t = i - 1; // 从当前位置的左边开始
            while (t >= 0 && heights[t] >= heights[i]) {
                // 如果左边下标对应的值更大
                // 则找到第一个小于这个值的新的下标
                t = min_left_index[t];
            }
            min_left_index[i] = t;
        }

        // 求每个位置右边第一个更小的元素的下标
        vector<int> min_right_index(len);
        min_right_index[len - 1] = len;
        for (int i = len - 2; i >= 0; i--) {
            int t = i + 1; // 从当前位置的右边开始
            while (t < len && heights[i] <= heights[t]) {
                // 如果当前位置元素值小于等于右边元素值
                // 则更新右边元素值下标
                t = min_right_index[t];
            }
            min_right_index[i] = t;
        }

        // 计算以每个柱子为高度的最大矩形面积
        int result = INT_MIN;
        for (int i = 0; i < len; i++) {
            int vol = heights[i] * (min_right_index[i] - min_left_index[i] - 1);
            result = max(result, vol);
        }

        return result;
    }
};

思路2：单调栈

上一题接雨水，如果想使用单调栈，就需要按行求雨水数，每一个位置向左和向右找到第一个大于当前位置的元素；

本题是找每个元素左右两边第一个小于当前元素的值。

1.单调栈中是什么：
保存的是每个位置的下标

2.单调栈的顺序：
由于本题要找左右两边第一个更小的元素，栈顶元素是待处理元素（即作为中间高度的位置），所以从栈顶到栈底应该是递减的，即从高到低，这样当遇到新元素大于栈顶元素时，由栈顶第二元素和新元素包围的栈顶元素构成以栈顶元素作为高度的最大矩形。

3.三种情况：（1）栈顶元素小于新元素：新元素入栈

（2）栈顶元素等于新元素：因为总是要找到当前元素更小的位置，因此两个相等的元素保留哪个都一样，所以删除栈顶元素，新元素入栈

（3）栈顶元素大于新元素：取出栈顶元素作为高度，新元素-栈顶第二元素的下标-1作为宽度计算面积。这里需要注意两个问题：如果一直不出现比栈顶元素更大的元素时，假设极端情况数组本身就是升序的，例如[2,4,6,8]，那么入栈之后都是单调递减，一直都没有走情况三计算结果的一步。所以最后应该在height末尾添加一个0（因为每个柱子都是非负值，遇到0就会进入情况3）；另一个问题是如果一直没有栈底第二个元素：如果数组本身是降序的，例如 [8,6,4,2]，在 8 入栈后，6 开始与8 进行比较，此时我们得到 mid（8），rigt（6），但是得不到 left。因此需要在height数组前面添加一个0.

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st; // 单调栈，存放高度下标，从栈顶到栈底递减
        heights.insert(heights.begin(), 0); // 在首部添加0，防止没有左边界
        heights.push_back(0); // 在尾部添加0，防止没有右边界
        int result = 0;

        st.push(0); // 第一个元素入栈
        for (int i = 1; i < heights.size(); i++) {
            int cur = heights[i]; // 当前高度
            if (heights[st.top()] < cur) {
                // 栈顶元素没有遇到更小的元素
                st.push(i);
            } else if (heights[st.top()] == cur) {
                // 栈顶元素遇到相等元素
                // 只保留后者即可
                // 因为都是以小于当前值的两侧作为边界
                st.pop();
                st.push(i);
            } else {
                while (!st.empty() && heights[st.top()] > cur) {
                    // 栈顶元素遇到小于自己的值
                    int mid = st.top();
                    st.pop();
                    // 栈顶第二元素也是小于栈顶元素的值
                    if (!st.empty()) {
                        int left = st.top();
                        int right = i;
                        int h = heights[mid];
                        int vol = h * (right - left - 1);
                        result = max(vol, result);
                    }
                } 
                st.push(i);
            }
        }
        
        return result;
    }
};