我的股票跨度问题算法为何错误？求排查逻辑问题

问题定义 #

股票跨度问题是一个金融问题：给定n天的股票每日价格序列，需计算所有n天的股票价格跨度。第i天的跨度Si定义为：当前天之前，股票价格小于等于当天价格的最大连续天数。例如，7天价格数组为{100, 80, 60, 70, 60, 75, 85}时，对应的跨度数组为{1, 1, 1, 2, 1, 4, 6}。

实现代码 #

class Solution {
    public static int[] calculateSpan(int price[], int n) {
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();
        int[] count = new int[price.length];
        
        for(int i = 0 ; i < n; i++) {
            int size = 0;
            
            while(!s1.empty() && price[i] > s1.peek()) {
                s2.push(s1.pop());
            }
            if(!s2.empty()) {
                size = s2.size();
            }
            while(!s2.empty() && price[i] > s2.peek()) {
                s1.push(s2.pop());
            }
            
            s1.push(price[i]);
            count[i] = size + 1;
        }
        
        return count;
    }
}

测试情况 #

输入 #

n = 134
74 665 742 512 254 469 748 445 663 758 38 60 724 142 330 779 317 636 591 243 289 507 241 143 65 249 247 606 691 330 371 151 607 702 394 349 430 624 85 755 357 641 167 177 332 709 145 440 627 124 738 739 119 483 530 542 34 716 640 59 305 331 378 707 474 787 222 746 525 673 671 230 378 374 298 513 787 491 362 237 756 768 456 375 32 53 151 351 142 125 367 231 708 592 408 138 258 288 554 784 546 110 210 159 222 189 23 147 307 231 414 369 101 592 363 56 611 760 425 538 749 84 396 42 403 351 692 437 575 621 597 22 149 800

我的输出 #

1 2 3 1 1 2 7 1 2 10 1 2 3 1 2 16 1 2 1 1 2 3 1 1 1 4 1 10 13 1 2 1 4 18 1 1 3 4 1 24 1 2 1 2 3 6 1 2 3 1 11 12 1 2 3 4 1 6 1 1 2 3 4 6 1 66 1 2 1 2 1 1 2 1 1 5 11 1 1 1 4 5 1 1 1 2 3 4 1 1 7 1 11 1 1 1 2 3 5 23 1 1 2 1 4 1 1 2 8 1 10 1 1 14 1 1 17 18 1 2 3 1 2 1 4 1 6 1 2 3 1 1 2 134

预期输出 #

1 2 3 1 1 2 7 1 2 10 1 2 3 1 2 16 1 2 1 1 2 3 1 1 1 4 1 10 13 1 2 1 4 18 1 1 3 4 1 24 1 2 1 2 3 6 1 2 3 1 11 12 1 2 3 4 1 6 1 1 2 3 4 6 1 66 1 2 1 2 1 1 2 1 1 5 77 1 1 1 4 5 1 1 1 2 3 4 1 1 7 1 11 1 1 1 2 3 5 23 1 1 2 1 4 1 1 2 8 1 10 1 1 14 1 1 17 18 1 2 3 1 2 1 4 1 6 1 2 3 1 1 2 134

问题分析 #

你代码的核心逻辑错误有两处，直接导致了输出中出现11而非预期77的问题：

1. 比较运算符错误，未处理价格相等的情况 #

问题定义中，跨度包含小于等于当前价格的连续天数，但你的代码中所有比较都用了>而非>=：

• 第一个while循环：price[i] > s1.peek()只会弹出比当前价格小的元素，遇到相等的元素会停止，导致相等的元素未被计入跨度。
• 第二个while循环：同样用>判断，导致s2中相等的元素无法被弹回s1，破坏后续栈的结构。

以测试用例中的第二个787为例，第一个787与当前价格相等，你的代码不会将其弹出到s2，因此s2的size仅统计了第一个787之后的10个元素，最终得到11，但实际上应该包含第一个787及之前所有小于等于它的元素，总数为76，加1后得到正确的77。

2. 双栈维护逻辑错误，破坏了单调栈的核心特性 #

你的代码在将s1中弹出的元素移到s2后，又将s2中比当前价格小的元素移回s1，这会导致s1不再是单调递减栈：

• 正确的单调栈思路是，栈中仅保留当前元素之前第一个更大的元素（及更大的元素），弹出的元素无需放回，因为它们的跨度已经被当前元素覆盖，后续元素只需基于当前元素的跨度计算即可。
• 而你的做法将弹出的小元素放回s1，导致栈中混入了比当前元素小的元素，后续处理时需要重复弹出这些元素，无法正确识别前面第一个更大的元素位置，也无法累加之前的跨度。

修正方向（仅针对当前双栈逻辑） #

如果要保留双栈结构，需做以下修改：

1. 将所有price[i] > x的判断改为price[i] >= x，覆盖价格相等的情况。
2. 移除第二个while循环，不再将s2中的元素移回s1，而是直接将当前元素压入s1，让s1维护一个单调递减栈（栈中元素从栈顶到栈底递减）。此时s2的size就是当前元素前面连续小于等于它的元素个数，加上1就是当天的跨度。

内容的提问来源于stack exchange，提问作者newLearner