【单调栈】快速查找边界

  • 单调递增栈:栈内元素单调递增的栈
  • 单调递减栈:栈内元素单调递减的栈
  • (单调递增栈为例)
  • 若新的元素比栈顶元素大,则入栈
  • 若新的元素较小,则持续弹出栈内元素,直到栈顶元素小于新元素
  • 保证栈内元素单调递增
  • 当元素出栈时:这个新元素是(第一个)出栈元素向后找第一个比它小的数
  • 当元素出栈后:这个新的栈顶元素是出栈元素向前找第一个比它小的数
  • 【单调栈】快速查找边界 - 图1
  • 模板:
  • 【单调栈】快速查找边界 - 图2