单调栈是为了解决两层foru循环O(n^2) 变为O(n)的问题
思路是:
-
维持一个单调栈.
-
依次进入单调栈,并淘汰对后续没有帮助的对象
-
当一个对象从栈里弹出的时候,结算当前对象参与的答案。
如何判断单调栈是大压小还是小压大呢?
-
左侧的要小的,就是大压小
-
左侧的要大的,就是小压大
思路是:
维持一个单调栈.
依次进入单调栈,并淘汰对后续没有帮助的对象
当一个对象从栈里弹出的时候,结算当前对象参与的答案。
左侧的要小的,就是大压小
左侧的要大的,就是小压大