Leetcode.901 股票价格跨度

题目信息

LeetoCode地址: . - 力扣（LeetCode）

题目理解

价格跨度的定义在题目中很明确，就是韭菜持有一只股票且该股票保持连续上涨最大的天数。

直观的想，我们可以保存第一天到当前天的所有股价，并一天一天往前找单调递减的连续天数。

但是考虑这样一个股价序列, 1,2,3,4,5,6,7,在计算6和7的股价跨度时，会存在大量的重复计算。

因为计算7的跨度时候，需要遍历到1，计算6的跨度时，也需要遍历到1。

让我们换一个思路。

假如后一天的股价比前一天小，则显然它的跨度就是1，此时我们需要将该天的股价和跨度缓存起来，因为后一天股价跨度的计算需要依赖它。

相反，假设后一天的股价比前一天大，显然它的跨度是之前所有的股价小于等于它的股价的跨度之和。

所以我们需要一个数据结构，当股价单调递减时，我们按照先后顺序缓存它们以及股价跨度1，一旦股价开始回升，我们就要从后向前从该数据结构中弹出所有更低股价的跨度，直到遇到一个更大的股价。相加的结果当然也要缓存进去，这显然就是一个栈，一个将单调递减数据连续入栈的单调栈。

这样处理的好处在于，没有任何计算是重复的，所有的跨度信息都被很好的保存，并在合适的时机删除（与更大的股价的跨度合并）。

单调栈写法

public class StockSpanner {    Deque stack;    public StockSpanner() {        stack = new LinkedList();    }    public int next(int price) {        if (stack.isEmpty()) {            stack.push(new int[]{price, 1});            return 1;        } else {            if (stack.peek()[0] > price) {                stack.push(new int[]{price, 1});                return 1;            }            int[] newTop = new int[]{price, 1};            while (!stack.isEmpty() && stack.peek()[0]