单调栈什么时候从后向前遍历，什么时候从前向后遍历?

一、单调栈什么时候从后向前遍历，什么时候从前向后遍历

如果是求右边的名列前茅个最大，那么就是从右向左遍历，构建单调递增栈。

如果是求右边的名列前茅个最小，那么就是从右向左遍历，构建单调递减栈。

如果是求左边的名列前茅个最大，那么就是从左向右遍历，构建单调递增栈。

如果是求左边的名列前茅个最小，那么就是从左向右遍历，构建单调递减栈。

单调栈

栈是我们都很熟悉的一种数据结构，特点就是先进后出。而单调栈就是这个栈中的元素大小还是单调的（递增或者递减）。单调栈对于处理 下一个更大/更小元素 有很高的效率。下面我们来介绍下。

单调递增栈：栈内的元素从栈顶到栈低是递增的。也就是栈顶的最小，栈底最大。

单调递减栈：栈内的元素从栈顶到栈底是递减的，也就是栈顶的最大，栈底最小。

构建单调栈模板

构建单调栈，就是有一个数字序列nums = [1,3,4,2]，根据该数字序列，来构建单调栈。

//构建单调递增栈

stack = []   //单调栈

numMap = {}   //记录下一个更大的元素

for index in range(len(nums)-1, -1, -1):

  while(len(stack) != 0 and stack[-1] <= nums[index]):

      //栈顶元素<=当前数据时，出栈，直到栈顶元素 大于 当前数据，当前数据入栈，才符合单调递增。

      stack.pop()

  if(len(stack) == 0):

      numMap[nums[index]] = -1

  else:

      numMap[nums[index]] = stack[-1]

  stack.append(nums[index])

延伸阅读：

二、栈是什么

栈是一种先进后出、后进先出的数据结构，栈和队列应该是最简单的两种数据结构了，其原理与实现非常简单。单调栈中的元素是严格单调递增或者递减的，也就是说：从栈底到栈顶，元素的值逐渐增大或者减小。虽然单调栈的性质很简单，但是其用处很大，可以用于求解元素的左右大小边界问题。