830.单调栈

#include <iostream>
using namespace std;
const int N = 100010;

int stk[N], tt;
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++ )
    {
        int x;
        cin >> x;
        while(tt && stk[tt] >= x) tt --;
        if (tt) cout << stk[tt] << ' ';
        else cout << -1 << ' ';
        stk[++ tt] = x;
    }
    return 0;
}

P5788 【模板】单调栈

#include <iostream>
using namespace std;
const int N = 3e6 + 10;

int stk[N], tt;
int a[N], f[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    
    
    for (int i = n; i >= 1; i --)
    {
        while (tt && a[stk[tt]] <= a[i]) tt --;
        if (tt) f[i] = stk[tt];
        else f[i] = 0;
        
        stk[++ tt] = i;
    }
    for (int i = 1; i <= n; i ++ ) cout << f[i] <<  ' ';
    return 0;
}

力扣：

大佬思路

  1. 739. 每日温度
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        vector<int> res(T.size());
        stack<int> stk;//存放索引
        for (int i = T.size() - 1; i >= 0; i -- )
        {
            while (!stk.empty() && T[stk.top()] <= T[i]) stk.pop();
            if (!stk.empty()) res[i] = stk.top() - i;
            else res[i] = 0;
            
            stk.push(i);
        }
        return res;
    }
};

503. 下一个更大元素 II

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        stack<int> stk;
        vector<int> res(n);
        for (int i = 2 * n - 1; i >= 0; i -- )
        {
            while (!stk.empty() && stk.top() <= nums[i % n]) stk.pop();
            if(!stk.empty()) res[i % n] = stk.top();
            else res[i % n] = -1;
            
            stk.push(nums[i % n]);
        }
        return res;
    }
};