在给定一天问前面有多少天比今天小的时候,可以尝试单调栈。首先要明确栈内一定每个元素都存在过所以可以保持一定的连续顺序。

递增or递减

递增

  1. 今天小于昨天, 那么答案就是1。并更新单调栈,维护递增(把比今天大的全部pop掉)
  2. 今天大于昨天,因为单调栈是递增关系我们没有办法知道是否有不在栈内的哪个点或许存在比今天还大的数。 所以递增不可以

递减

  1. 今天小于昨天, 那么答案就是1。把自己加入单调栈
  2. 今天大于昨天,因为单调栈是递减关系,我们在维护单调栈性质的时候顺便更新有多少天。i.e. 如果比昨天小的有3天,那么我们加上3天。这个3天就告诉了我们在维护单调栈性质时,有3天被昨天pop掉了。然后我们继续看4天前是否比今天大,如果小那么继续加上比4天前小的天数。 所以用递减的单调栈