单调栈，对应博弈论中消除被占优选项后的未被占优选项（undominated）。

递减栈 <=> 找波谷localMin <=> 数组中下一个更大的数

找下一个更大的数，当前数>栈顶时就弹出栈顶，弹不动了再入栈。当前数入栈时<=栈顶，栈中是个递减序列，栈顶是最小值。弹出数是被占优的数，表示找到了"下一个更大的数"。栈中数是未被占优的数，表示还没有找到“下一个更大的数"。

考查当前数、弹出数、新栈顶三个数：

  • 新栈顶>=弹出数<当前数，弹出数是波谷、局部最小值。
  • 弹出数<当前数，这是硬约束。若继续弹出，弹出数是不断"抬高"的波谷，最后的弹出数是左侧<当前数的最大值。新栈顶会变大，最后新栈顶是>=当前数的最小值。即紧邻的三个数：最后弹出数 < 当前数 <= 最后新栈顶，半开半闭。对应下面的代码，

注：正常在当前数>栈顶时弹出，留下（非严格）单调递减栈（相等数都留下）；若当前数>=栈顶时弹出，留下严格单调递减栈（相同数留下最右边的）；偶尔，若要相同数留下最左边的，那么：1. 当前数>栈顶时弹出；2. 当前数!=栈顶才push()入栈。

vector<int> dailyTemperatures(vector<int>& T) {
    const int N = T.size();
    vector<int> ans(N, 0);
    stack<int> stk;
    for (int i = 0; i < N; i++) {
        while (!stk.empty() && T[i] > T[stk.top()]) {
            int pop = stk.top(); stk.pop();
            ans[pop] = i - pop;
        }
        stk.push(i);
    }
    return ans;
}

循环数组中下一个更大的数

循环数组的通用处理是把数组拼两次

vector<int> nextGreaterElements(vector<int>& nums) {
    const int N = nums.size();
    vector<int> ans(N, -1);
    stack<int> stk; // 找下一个更大元素，保存下标
    // 循环数组，查找两遍nums[]
    for (int i = 0; i < 2 * N; i++) {
        while (!stk.empty() && nums[i % N] > nums[stk.top()]) {
            ans[stk.top()] = nums[i % N];
            stk.pop();
        }
        if (i < N) stk.push(i); // 前N个数才找
    }
    return ans;
}

132模式

  • https://leetcode.com/problems/132-pattern/
bool find132pattern(vector<int>& nums) {
	// 132模式：顺序三个数a1、a2、a3，a1<a3<a2。
	// 对于第二个数a2，在右边找下一个更小的数a3，再看左边是否有数<a3。
	// a2右边下一个更小的数a3 <=等价于=> 从右往左，a3找下一个更大的数a2
	const int N = nums.size();
	int a3 = INT_MIN;
	stack<int> stk;
	for (int i = N - 1; i >= 0; i--) {
		if (nums[i] < a3) return true;  // i--后进新循环，nums[i]是a1

		while (!stk.empty() && nums[i] > stk.top()) {  // nums[i]是a2
			a3 = stk.top();
			stk.pop();
		}
		stk.push(nums[i]);
 }
	return false;
}

延伸：123模式简单得多

bool increasingTriplet(vector<int>& nums) {
    // 从左到右扫描，若开始设置第三小，说明前面已有min1和min2
    int min1 = INT_MAX, min2 = INT_MAX;
    for (int num : nums) {
        if (num <= min1) {
            min1 = num;
        } else if (num <= min2) {
            min2 = num;
        } else {
            return true;
        }
    }
    return false;
}

数组对应的最小代价树

int mctFromLeafValues(vector<int> &arr) {
	// 题目：数组对应叶节点值的中序遍历，内节点代价=左右子树最大叶节点之积，
	//      总代价=内节点代价之和，求所有树结构中的最小总代价。
	// 转化：每次从两个邻居节点a和b中删除min(a,b)，代价为a*b，
	//      求所有删除顺序中代价最小的。
	// 每次删除局部最小值（波谷）
	int ans = 0;
	stack<int> stk;
	stk.push(INT_MAX);  // 左哨兵
	for (int val : arr) {
		while (!stk.empty() && val > stk.top()) {
			int localMin = stk.top();
			stk.pop();
			ans += localMin * min(stk.top(), val);
		}
		stk.push(val);
	}
	// 递减栈，栈顶是最小值
	while (stk.size() > 2) {
		int localMin = stk.top();
		stk.pop();
		ans += localMin * stk.top();
	}
	return ans;
}

柱状图储水问题

参见同名笔记

递增栈 <=> 找波峰localMax <=> 数组中下一个更小的数

同样有结论：

  • 弹出数是波峰、局部最大值
  • 最后弹出数是左侧>当前数的最小值
  • 紧邻的三个数：最后弹出数 > 当前数 >=最后新栈顶，半开半闭

柱状图中的最大矩形

最大矩形找"波峰"，刚好形状相似。储水问题找“波谷”，刚好也形状相似。

参见：全是1的子矩阵