第二章：特殊数据结构：单调栈

labuladong 特殊数据结构：单调栈

栈（stack）是很简单的一种数据结构，先进后出的逻辑顺序，符合某些问题的特点，比如说函数调用栈。单调栈实际上就是栈，只是利用了一些巧妙的逻辑，使得每次新元素入栈后，栈内的元素都保持有序（单调递增或单调递减）

文章例题：
给你一个数组 [2,1,2,4,3]，你返回数组 [4,2,4,-1,-1]。
解释：第一个 2 后面比 2 大的数是 4; 1 后面比 1 大的数是 2；第二个 2 后面比 2 大的数是 4; 4 后面没有比 4 大的数，填 -1；3 后面没有比 3 大的数，填 -1。

这个问题可以这样抽象思考：把数组的元素想象成并列站立的人，元素大小想象成人的身高。这些人站成一列，如何求元素「2」的 Next Greater Number 呢？很简单，如果能够看到元素「2」，那么他后面可见的第一个人就是「2」的 Next Greater Number，因为比「2」小的元素身高不够，都被「2」挡住了，第一个露出来的就是答案。

这就是单调栈解决问题的模板。for 循环要从后往前扫描元素，因为我们借助的是栈的结构，倒着入栈，其实是正着出栈。while 循环是把两个“高个”元素之间的元素排除，因为他们的存在没有意义，前面挡着个“更高”的元素，所以他们不可能被作为后续进来的元素的 Next Great Number 了。

P.S., 也可以用“压扁思想”理解（倒序遍历）：
3没有东西压扁，栈为空，所以对应-1。然后3进栈，此时栈为[3]
4能压扁3，pop后栈为空，所以对应-1。然后4进栈,此时栈为[4]
2不能压扁4，不能pop，栈为[4],所以对应4。然后2进栈，此时栈为[4,2]
1不能压扁2和4，不能pop，栈为[4,2],所以对应2。然后1进栈，此时栈为[4,2,1]
2能压扁1,2,不能压扁4，栈为[4],所以对应4。然后2进栈，此时栈为[4,2]

def nextGreaterElement(nums):
    ans=[-1 for _ in range(len(nums))]
    s=[]
    for i in range(len(nums)-1,-1,-1):#倒着往栈里放
        print(s)
        while s and s[-1]<=nums[i]:#矮个起开
            s.pop()
        ans[i]=s[-1] if  s else -1
        s.append(nums[i]) # 进队，接受之后的身高判定
    return ans

nums=[2, 1, 2, 4, 3]
print("ans:",nextGreaterElement(nums))

结果输出（栈里的元素始终单调递减）：

每次的s:
[]
[3]
[4]
[4, 2]
[4, 2, 1]

ans: [4, 2, 4, -1, -1]

503. 下一个更大元素 II

• 从最后一个元素开始逆序遍历，维护一个单调递减的栈。
• 因为这个栈是先进后出，且单调递减的，所以弹出栈中小于等于当前元素的值后，栈顶的元素就是找到的结果
• 把当前元素入栈，这样，它前面的元素才能和它继续比较
• 根据不同输出结果的要求，栈中存放当前元素对应的信息，此题存放当前元素

以 [2,1,2,4,3] 为例，nums*2 后得[2,1,2,4,3,2,1,2,4,3] （扩充数组，以便求取最后一个值对应的结果）。
当前值对应的结果为栈中当前值所在的前一个元素（记录结果后才把当前值入栈），当前值前面没有元素，则结果为-1

则逆序遍历过程中：
当前值为：3，加入当前值后对应的栈为[3] （无解，-1）
当前值为：4，加入当前值后对应的栈为[4] （无解，-1）
当前值为：2，加入当前值后对应的栈为[4, 2]
当前值为：1，加入当前值后对应的栈为[4, 2, 1]
当前值为：2，加入当前值后对应的栈为[4, 2]
当前值为：3，加入当前值后对应的栈为[4, 3]
当前值为：4，加入当前值后对应的栈为[4] （无解，-1）
当前值为：2，加入当前值后对应的栈为[4, 2]
当前值为：1，加入当前值后对应的栈为[4, 2, 1]
当前值为：2，加入当前值后对应的栈为[4, 2]

class Solution(object):
    def nextGreaterElements(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if not nums: return []
        nums=nums*2  # 扩充数组
        ans=[-1 for _ in range(len(nums))] # 初始化
        s=[]
        for i in range(len(nums)-1,-1,-1): # 逆序遍历
            while s and nums[i]>=s[-1]: # 1.弹出栈中小于等于当前元素的值
                s.pop()
            ans[i]=s[-1] if s else -1 # 2.弹出不符合的元素后，栈顶元素就是所求的结果
            s.append(nums[i]) # 3. 当前元素入栈，这样，它前面的元素才能和它继续比较
        return ans[0:len(nums)//2]

//#include <vector>
//#include <stack>
//#include <iostream>
//using namespace std;

class Solution {
public:
    vector<int> nextGreaterElements(vector<int> &nums) {
//        把数组扩大到两倍
        vector<int> nums1 = nums; // 或者vector<int> nums1(nums.begin(), nums.end());
        nums.insert(nums.end(), nums1.begin(), nums1.end());
        vector<int> ans(nums.size(), -1);//保存结果
        stack<int> s; // 单调递减的栈
        for (int i = nums.size() - 1; i >= 0; --i) {
//            压扁栈中比nums[i]小的数
            while (!s.empty() && nums[i] >= s.top()) {
                s.pop();
            }
            ans[i] = s.empty() ? -1 : s.top(); // 尽量压扁后，第i个位置的结果就是栈顶的数字
            s.push(nums[i]); // 当前元素入栈，这样，它前面的元素才能和它继续比较
        }
        ans.resize(nums.size() / 2); // 取前一半的结果
        return ans;
    }
};

//int main() {
//    Solution s;
//    vector<int> nums = {1, 2, 1};
//    vector<int> ans = s.nextGreaterElements(nums);
//    for (auto &i:ans) {
//        cout << i <<endl;
//    }
//}

496. 下一个更大元素 I

• 该题与上题的区别是：
  • 上题直接给定列表，在逆序遍历的同时，更新单调栈
  • 本题中，对任意的nums1[i], 需要找到当前元素在nums2 中的位置，并把该位置及其后面的元素取出来并反转后作为栈s 中的内容 （nums2[nums2.index(nums1[i]):][::-1]）,然后进行比较。
    • （这里并不是维护单调递减的栈，而是把找到的反转栈从尾部开始逐个弹出不符合条件的元素，最终得到结果）
  • 根据不同输出结果的要求，栈中存放当前元素的信息，此题存放当前元素在nums2中对应的本身及其后面的元素（并反转）

以 nums1=[4,1,2]， nums2=[1,3,4,2] 为例，
则逆序遍历过程中：
当前值为2,对应的反转后的栈为[2]
当前值为1,对应的反转后的栈为[2, 4, 3, 1]
（解释：nums2中找到1的位置，1及其1后面的元素为[1,3,4,2],反转后为[2,4,3,1]）
当前值为4,对应的反转后的栈为[2, 4]

class Solution(object):
    def nextGreaterElement(self, nums1, nums2):
        if not nums1: return [] #若为空数组，则返回
        ans=[-1 for _ in range(len(nums1))]
        for i in range(len(nums1)-1,-1,-1):#逆序遍历
            # 用反转，使得pop的顺序一致
            # 比如1 要和[1,3,4,2]比，输出3
            # 则反转后为[2,4,3,1], 弹1，得到3为符合条件的值
            s=nums2[nums2.index(nums1[i]):][::-1] # 找到每个元素对应的栈，并反转
            while s and nums1[i]>=s[-1]: # 1.弹出栈中小于等于当前元素的值
                s.pop()#矮个起开
            ans[i]=s[-1] if s else -1 # 2.弹出不符合的元素后，栈顶元素就是所求的结果
        return ans

739.每日温度

• 用栈记录的是list中元素的index，而不是list中元素值本身 （与503题类似，根据不同输出结果的要求，栈中存放当前元素的信息，此题存放当前元素的index下标）

class Solution(object):
    def dailyTemperatures(self, T):
        """
        :type T: List[int]
        :rtype: List[int]
        """
        if not T :return []
        ans=[0 for _ in range(len(T))]
        s=[]# 这里放元素索引，而不是元素
        for i in range(len(T)-1,-1,-1):
            while s and T[i]>=T[s[-1]]:
                s.pop()
            ans[i]=s[-1]-i if s else 0 # 得到索引间距
            s.append(i)# 放入索引
        # print(ans)
        return ans
T=[73, 74, 75, 71, 69, 72, 76, 73]
so=Solution()
so.dailyTemperatures(T)