LeetCode、901. 股票价格跨度【中等，单调栈】

文章目录

前言
LeetCode、901. 股票价格跨度【中等，单调栈】
- 题目链接及分类
- 思路
- - 思路1：暴力
  - 思路2：单调栈写法
  - 优化：单调栈简化写法(数组替代栈集合)
资料获取

前言

博主介绍：✌目前全网粉丝2W+，csdn博客专家、Java领域优质创作者，博客之星、阿里云平台优质作者、专注于Java后端技术领域。

涵盖技术内容：Java后端、算法、分布式微服务、中间件、前端、运维、ROS等。

博主所有博客文件目录索引：博客目录索引(持续更新)

视频平台：b站-Coder长路

LeetCode、901. 股票价格跨度【中等，单调栈】

题目链接及分类

题目链接：LeetCode、901. 股票价格跨度

分类：数据结构/栈/单调栈

思路

思路1：暴力

复杂度分析：n次next()为时间复杂度O(n²)

class StockSpanner {

    private List<Integer> list;

    //1万数据量，O(n)、O(nlogn)
    //题意：找到距离当前的最大连续长度
    public StockSpanner() {
        list = new ArrayList<>();
    }
    
    //暴力O(n)
    public int next(int price) {
        int count = 1;
        for (int i = list.size() - 1; i >= 0; i--) {
            if (list.get(i) <= price) count++;
            else break;
        }
        list.add(price);
        return count;
    }
}

思路2：单调栈写法

复杂度分析：n次next()为时间复杂度O(n)

class StockSpanner {

    private Stack<Pair<Integer, Integer>> stack = new Stack<>();

    //1万数据量，O(n)、O(nlogn)
    public StockSpanner() {
    }
    
    //数据集 及  结果集
    //[100,80,60,70,60,75,85]   [1,1,1,2,1,4,6]
    //处理的过程：
    //(100,1)、(80, 1)、(60, 1)
    //(100,1)、(80,1)、(70, 2)、(60, 1)
    //(100,1)、(80,1)、(70, 2)、(75，2)
    //(100,1)、(85，6)
    //单调栈解法
    //记录两个值(price价格、和当日价格的跨度)
    //每次next()的时间复杂度O(1)，那么n次next()调用就是O(n)的复杂度
    public int next(int price) {
        int res = 1;
        //维护一个最大值
        while (!stack.isEmpty() && price >= stack.peek().getKey()) {
            int len = stack.peek().getValue();
            //弹出当前的
            stack.pop();
            res += len;
        }
        //入栈
        stack.push(new Pair<Integer, Integer>(price, res));
        return res;
    }
}

优化：单调栈简化写法(数组替代栈集合)

效果：减少了入栈出栈的开销

复杂度分析：n次next()为时间复杂度O(n)

class StockSpanner {

    //存储价格
    private int[] prices = new int[10000];
    //存储对应价格当前的跨度
    private int[] lens = new int[10000];
    //表示当前的指针位置
    private int pos = -1;

    public StockSpanner() {
    }
    
    //学习题解：https://leetcode.cn/submissions/detail/375037369/
    //price next pos
    //100   1     0
    //80    1     1
    //60    1     2  
    //70    2     3
    //60    1     4
    //75    4     5
    //85    6     6
    public int next(int price) {
        int res = 1;//初始值
        //计算跨度
        int cur = pos;
        //单调栈（注意cur -= lens[cur]，下次定位就直接定位到该元素位置-跨度的地方再做比较）
        while (cur >= 0 && price >= prices[cur]) {
            cur -= lens[cur];
        }
        //记录[cur, pos]的长度(也就是之间的跨度)
        res += (pos - cur);
        //记录价值以及跨度
        ++pos;
        prices[pos] = price;
        lens[pos] = res;
        return res;
    }
}