LeetCode 901. 股票价格跨度

Categories:

题目描述
思路分析
1. 解法一：单调栈（推荐）
相似题目

题目描述

✅ 901. 股票价格跨度

思路分析

解法一：单调栈（推荐）

核心思路：

栈中保存 (price, span)，保证价格单调递减。

新价格到来时，弹出所有 price <= current 的元素并累加跨度。

当前跨度入栈即可。

复杂度分析：

时间复杂度：O(1) 均摊。

空间复杂度：O(n)，其中 n 表示天数。

import java.util.ArrayDeque;
import java.util.Deque;

class StockSpanner {
    private final Deque<int[]> stack = new ArrayDeque<>();

    public int next(int price) {
        int span = 1;
        while (!stack.isEmpty() && stack.peek()[0] <= price) {
            span += stack.pop()[1];
        }
        stack.push(new int[]{price, span});
        return span;
    }
}

type StockSpanner struct {
	stack [][2]int
}

func Constructor() StockSpanner {
	return StockSpanner{stack: make([][2]int, 0)}
}

func (s *StockSpanner) Next(price int) int {
	span := 1
	for len(s.stack) > 0 && s.stack[len(s.stack)-1][0] <= price {
		span += s.stack[len(s.stack)-1][1]
		s.stack = s.stack[:len(s.stack)-1]
	}
	s.stack = append(s.stack, [2]int{price, span})
	return span
}

相似题目

题目	难度	考察点
496. 下一个更大元素 I	简单	单调栈
503. 下一个更大元素 II	中等	单调栈
739. 每日温度	中等	单调栈
84. 柱状图中最大的矩形	困难	单调栈
402. 移掉 K 位数字	中等	单调栈

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/99351946