两种角度理解单调栈（下一个更大元素）

1. 从右到左，栈中记录的是下一个更大元素的候选项，由于左边更大的会挡住，所以右边的是无效的，出栈

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [-1] * n
        st = []
        for i in range(n * 2 - 1, -1, -1):
            x = nums[i % n]
            while st and x >= st[-1]:
                # 由于 x 的出现，栈顶元素永远不会是左边元素的「下一个更大元素」
                st.pop()
            if st and i < n:
                ans[i] = st[-1]
            st.append(x)
        return ans

2. 从左到右，栈中记录还没算出下一个更大元素的那些下标，只要遍历到比栈顶大的，栈中的数就找到答案了，出栈

func nextGreaterElements(nums []int) []int {
    n := len(nums)
    ans := make([]int, n)
    for i := range ans {
        ans[i] = -1
    }
    st := []int{}
    for i := 0; i < 2 * n; i++ {
        x := nums[i % n]
        for len(st) > 0 && x > nums[st[len(st)-1]] {
            // x 是 nums[st[len(st)-1]] 的下一个更大元素
            // 既然 nums[st[len(st)-1]] 已经算出答案，则从栈顶弹出
            ans[st[len(st)-1]] = x
            st = st[:len(st)-1]
        }
        if i < n {
            st = append(st, i)
        }
    }
    return ans
}

---

通过例题来看：

给定一个整数数组 A，你可以从某一起始索引出发，跳跃一定次数。在你跳跃的过程中，第 1、3、5... 次跳跃称为奇数跳跃，而第 2、4、6... 次跳跃称为偶数跳跃。

你可以按以下方式从索引 i 向后跳转到索引 j（其中 i < j）：

• 在进行奇数跳跃时（如，第 1，3，5... 次跳跃），你将会跳到索引 j，使得 A[i] <= A[j]，A[j] 是可能的最小值。如果存在多个这样的索引 j，你只能跳到满足要求的最小索引 j 上。
• 在进行偶数跳跃时（如，第 2，4，6... 次跳跃），你将会跳到索引 j，使得 A[i] >= A[j]，A[j] 是可能的最大值。如果存在多个这样的索引 j，你只能跳到满足要求的最小索引 j 上。

题意是要求出每个数当前位置后，大于等于它的数中值最小且索引最小的位置，以及小于等于它的数中值最大且索引最小的位置。在排序之后，只要在 idx 数组中找到第一个比当前索引大的索引，它就代表了当前索引的后继。首先将下标进行排序，然后通过单调栈解决

vector<int> get(vector<int>& idx)
{
    int n = idx.size();
    vector<int> res(n, -1);
    stack<int> s;
    for (int i = 0; i < n; i++)
    {
        while (s.size() && s.top() < idx[i]) 
        {
            res[s.top()] = idx[i];
            s.pop();
        }
        s.push(idx[i]);
    }
    return res;
}
// main(vector<int>& arr)
int n = arr.size();
vector<int> idx(n);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int a, int b)
{
    return arr[a] < arr[b] || (arr[a] == arr[b] && a < b);
});
vector<int> nxtlarger = get(idx);

sort(idx.begin(), idx.end(), [&](int a, int b)
{
    return arr[a] > arr[b] || (arr[a] == arr[b] && a < b);
});
vector<int> nxtsmaller = get(idx);

还可以用 map 来求

map<int, int> m;
for (int i = n - 1; i >= 0; i--)
{
    auto it = m.lower_bound(arr[i]);
    if (it != m.end())
    {
        int nxtlarger_idx = it->second; 
    }
    it = m.lower_bound(-arr[i]);
    if (it != m.end() && it->first <= 0)
    {
		int nxtsmaller_idx = it->second;
    }
    m[arr[i]] = i;
    m[-arr[i]] = i;
}

---

还有一类题是这样的：求出一个子数组内【满足A性质】的个数 - 【不满足A性质】的个数的差，然后问这个差最大是多少。 首先进行等价转换，满足性质 => nums[i] = 1 ，反之 nums[i] = -1 ，问题变为求最长子数组，其元素和大于 0。然后利用前缀和，变为找到两个下标 且 ，最大化 的值。 分析：哪些下标可以作为左端点？仅当它左边没有比它更小的数 => 单调栈！然后枚举右端点，并更新答案即可

vector<int> sum(n + 1);
stack<int> s;
int res = 0;
for (int i = 1; i <= n; i++)
    sum[i] = sum[i - 1] + (f(nums[i - 1] ? 1 : -1));
for (int i = 0; i <= n; i++)
    if (s.empty() || sum[s.top()] > sum[i]) s.push(i);
for (int i = n; i >= 0; i--) // 倒序遍历
    while (s.size() && sum[s.top()] < sum[i]) 
    {
        res = max(res, i - s.top());
        s.pop();
    }
return res;

---

经典应用：

给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。

用贡献法，定义 对应的边界为开区间 ，对答案的贡献为 ，注意如果左侧没有，则 ，右侧没有则 。当数组有重复元素时，需要修改边界定义，把右边界定义为 【小于等于 的数的下标】，用单调栈两次遍历的版本如下：

const int MOD = 1e9+7;
typedef long long LL;
int sumSubarrayMins(vector<int>& arr) {
    int n = arr.size();
    stack<int> s;
    vector<int> left(n, -1);
    vector<int> right(n, n);
    for (int i = 0; i < n; i++) 
    {
        while (s.size() && arr[s.top()] > arr[i]) 
        {
            right[s.top()] = i; 
            // 对于栈顶元素 t，如果 t 右侧有多个小于或等于 t 的元素，
            // 那么 t 只会因为右侧第一个小于或等于 t 的元素而出栈，这恰好符合右边界的定义
            s.pop();
        }
        if (s.size()) left[i] = s.top();
        s.push(i);
    }

    LL res = 0;
    for (int i = 0; i < n; i++)
        res = (res + LL(i - left[i]) * (right[i] - i) * arr[i] % MOD) % MOD; 
    	//两次取模
    return res % MOD; 
}

---