单调栈练习题

柱状图中最大矩形

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

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

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例:

输入: [2,1,5,6,2,3]
输出: 10

分析：

单调栈模板(以单调递增栈为例)：

  1. 若当前元素大于等于栈顶元素，加入栈
  2. 若当前元素小，则弹出栈顶元素，继续比较，直到它也入栈
stack<int> st;
for(int i = 0; i < nums.size(); i++)
{
    while(!st.empty() && st.top() > nums[i])
    {
        st.pop();
    }
    st.push(nums[i]);
}

单调栈性质：

  1. 栈内的元素是递增的
  2. 当元素出栈时，说明这个新元素是出栈元素向后找第一个比其小的元素
  3. 当元素出栈后，说明新栈顶元素是出栈元素向前找第一个比其小的元素

求面积：

要在弹出时求当前的面积：

  1. 矩形框为弹出元素的高
  2. 左边界为 弹出的栈顶元素下标，右边界为 i-1
  3. 面积为max(ans, (right - left + 1) * heights[cur])
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int ans = 0;
        stack<int> st;
        heights.insert(heights.begin(), 0);//在向量最前面插入0
        heights.push_back(0);//在向量最后面插入0
         for (int i = 0; i < heights.size(); i++)
            {//st.back()存的是栈顶元素的height[]数组下标，heights[st.back()]为单调递增栈的栈顶元素
                while (!st.empty() && heights[st.top()] > heights[i])
                    {//栈非空且当前元素小于栈顶元素，则弹出栈顶元素，并且计算面积
                        int cur = st.top();
                        st.pop();//弹出栈
                        int left = st.top() + 1;//左边界为 新的栈顶元素下标+1
                        int right = i - 1;//右边界为 i-1
                        ans = max(ans, (right - left + 1) * heights[cur]);
                     }
                st.push(i);
            }
        return ans;
    }
};

​

逛街

小Q在周末的时候和他的小伙伴来到大城市逛街，一条步行街上有很多高楼，共有n座高楼排成一行。

小Q从第一栋一直走到了最后一栋，小Q从来都没有见到这么多的楼，所以他想知道他在每栋楼的位置处能看到多少栋楼呢？（当前面的楼的高度大于等于后面的楼时，后面的楼将被挡住

输入描述:
输入第一行将包含一个数字n，代表楼的栋数，接下来的一行将包含n个数字wi(1<=i<=n)，代表每一栋楼的高度。
1<=n<=100000;
1<=wi<=100000;

输出描述:

输出一行，包含空格分割的n个数字vi，分别代表小Q在第i栋楼时能看到的楼的数量。

示例1

输入

6
5 3 8 3 2 5

输出

3 3 5 4 4 4

说明
当小Q处于位置3时，他可以向前看到位置2,1处的楼，向后看到位置4,6处的楼，加上第3栋楼，共可看到5栋楼。当小Q处于位置4时，他可以向前看到位置3处的楼，向后看到位置5,6处的楼，加上第4栋楼，共可看到4栋楼。

思路：

到每一个点x[i]时，计算x[0：i-1]以x[i-1]为终点的单调递减序列的最大长度以及以x[i+1]为起点的单调递增序列长度，将他们相加再加1即是可以看到的楼的数目

使用单调栈来计算单调递增递减序列长度

a[i] 表示以x[i]为终点的单调递减栈的长度大小：

i从0~n-1的顺序遍历：当扫描的元素x[i]大于栈顶元素的时候，弹出栈顶元素直到有比x[i]大的元素才入栈，此时栈中就是以x[i]为终点的单调递减栈；

j从后往前的顺序（ n-1 ~ 0 ）遍历：当扫描的元素x[j]]大于栈顶元素的时候，弹出栈顶元素直到有比x[j]大的元素才入栈，此时栈中就是以x[j]为起点的单调递增栈；

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
vector<int> a, b;
stack<int> st1, st2;
int main() {
    int n, x[100001];
    cin >> n;
    int ans = 0;
    for (int i = 0; i < n; i++) cin >> x[i];
    for (int i = 0, j = n - 1; i < n, j >= 0; i++, j--) {
        a.push_back(st1.size());
        b.push_back(st2.size());
        while (!st1.empty() && st1.top() <= x[i]) st1.pop();
        while (!st2.empty() && st2.top() <= x[j]) st2.pop();
        st1.push(x[i]);
        st2.push(x[j]);
    }
    reverse(b.begin(), b.end());//由于b是从n-1开始往前计算的，所以需要翻转
    for (int i = 0; i < n; i++) cout << b[i] + a[i] + 1<< " ";
    return 0;
}

739 每日温度

请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

方法：

维护一个单调栈，存储单调递减的温度（下标），从第一天的温度开始：

  • 如果栈为空，则加入当前扫描的温度

  • 如果栈不为空：

    • 如果扫描的温度大于栈顶的温度，说明当前扫描的温度是栈顶温度之后第一个大于它的温度，计算他们的日期之差，存入到ans[previousIndex]中；
    • 如果扫描的温度小于等于栈顶的温度，说明当前的温度太低，直接入栈
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        int n = T.size();
        vector<int> ans(n);
        stack<int> s;
        for(int i = 0;i < n;++i){
            while(!s.empty() && T[i] > T[s.top()]){
                int previousIndex = s.top();
                ans[previousIndex] = i - previousIndex;
                s.pop();
            }
            s.push(i);
        }
        return ans;
    }
};

901 股票的价格跨度

编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。

今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。

例如，如果未来7天股票的价格是 [100, 80, 60, 70, 60, 75, 85]，那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。

示例：

输入：["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
输出：[null,1,1,1,2,1,4,6]
解释：
首先，初始化 S = StockSpanner()，然后：
S.next(100) 被调用并返回 1，
S.next(80) 被调用并返回 1，
S.next(60) 被调用并返回 1，
S.next(70) 被调用并返回 2，
S.next(60) 被调用并返回 1，
S.next(75) 被调用并返回 4，
S.next(85) 被调用并返回 6。

注意 (例如) S.next(75) 返回 4，因为截至今天的最后 4 个价格
(包括今天的价格 75) 小于或等于今天的价格。

算法：

我们用单调栈维护一个单调递减的价格序列，并且对于每个价格，存储一个weight表示它离上一个价格之间（即最近的一个大于它的价格之间）的天数。如果是栈底的价格，则存储它本身对应的天数。例如 [11, 3, 9, 5, 6, 4, 7] 对应的单调栈为 (11, weight=1), (9, weight=2), (7, weight=4)。

当我们得到了新的一天的价格，例如 10，我们将所有栈中所有小于等于 10 的元素全部取出，将它们的 weight 进行累加，再加上 1 就得到了答案。在这之后，我们把 10 和它对应的 weight 放入栈中，得到 (11, weight=1), (10, weight=7)。

class StockSpanner {
private:
    stack<int> weight;
    stack<int> stock;
public:
    StockSpanner() {
    }
    
    int next(int price) {
        int ans = 1;
        while(!weight.empty()  && !stock.empty() && price >= stock.top() ){
            ans += weight.top();
            weight.pop();
            stock.pop();
        }
        weight.push(ans);
        stock.push(price);
        return ans;
    }
};


/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner* obj = new StockSpanner();
 * int param_1 = obj->next(price);
 */
最后修改：2020 年 07 月 13 日 07 : 28 PM
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏