1.题目

编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。

今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。

例如，如果未来7天股票的价格是 [100, 80, 60, 70, 60, 75, 85]，那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。

示例：

输入：["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]

输出：[null,1,1,1,2,1,4,6]

解释：

首先，初始化 S = StockSpanner()，然后：

S.next(100) 被调用并返回 1，

S.next(80) 被调用并返回 1，

S.next(60) 被调用并返回 1，

S.next(70) 被调用并返回 2，

S.next(60) 被调用并返回 1，

S.next(75) 被调用并返回 4，

S.next(85) 被调用并返回 6。

注意 (例如) S.next(75) 返回 4，因为截至今天的最后 4 个价格

(包括今天的价格 75) 小于或等于今天的价格。

2.思路

可以考虑使用单调栈来记录最近的股票价格，使用单调递减栈记录之前的股票价格，如果今天价格小于栈顶元素，说明，今天价格比之前最近的价格要低，直接计算为1，然后入栈。如果今天价格比栈顶元素价格高，就循环计算出栈，根据下标差值可以计算出最大连续日数。然后再入栈。

时间复杂度O(n)

空间复杂度O(n)

3.题解

题解如下

class StockSpanner {

   Deque<Integer> stack;

   List<Integer> list;

   public StockSpanner() {

       stack = new LinkedList();

       list = new ArrayList();

   }

   public int next(int price) {

       list.add(price);

       while(!stack.isEmpty() && price >= list.get(stack.peek())) {

           stack.pop();

       }

       int index = stack.isEmpty() ? 0 : stack.peek() + 1;

       int ans = list.size() - index;

       stack.push(list.size() - 1);

       return ans;

   }

}

本文地址： https://www.tuifuli.net/article-show-id-1288.html