单调栈

优质参考博客

• 单调栈

重要性质

• 弹出时只能从栈顶[st.top()]弹出
• 从栈顶到栈底，元素大小呈某种单调趋势
• 当欲压入栈的元素不满足这个单调性时，就要把不满足单调性的所有[栈顶]元素弹出 -> 这个性质用到的比较多
• 配合数组使用时，栈内可以存储对应元素的下标，而不是元素值

使用心得

• 使用时要注意考虑单调顺序：1️⃣递增，2️⃣递减
• 要搞清楚单调栈中记录元素的意义：例如题—[503]，单调栈中记录的是还没有找到下一个更大值的下标, 只要遍历到比栈顶元素值更大的数，就意味着栈顶元素找到了答案，记录答案，然后从栈顶弹出
• 一定要注意单调栈里存储的是索引还是元素值

相关题目

• 503.下一个更大元素2
• 556.下一个更大元素3: 变形题，比较有意思！！！

题目解析

• [556] 一定要注意题目的条件 ->
  • 满足条件的最小整数
  • 如果最小的不是32位整数，也返回-1

扩展-循环数组

• 处理方式1：将[0:n-1]个个数顺序拷贝到第n个数后面，构成一个普通数组
• 处理方式2：遍历[0:2n-1)次，取元素时对下标取模