下一个更大元素的单调栈解法

单调栈的适用原因

这类题目本质上是在维护一个“还没找到答案的元素集合”。单调栈能把这些元素按一定顺序保存起来，当新元素出现时，可以一次性解决一批比它小的元素。相比逐个向右扫描的暴力做法，单调栈能把重复比较压缩掉，整体效率更高，常见情况下可以做到 O(n)。

推荐保存下标

通常更推荐保存下标，因为下标不仅能拿到元素值，还能定位结果要写回的位置。这样在需要构造答案数组时会更方便，也更容易处理重复值。只有在题目只关心数值、不关心位置时，才更适合直接存元素值。

重复元素的处理

不会，只要比较条件写对。做“下一个更大元素”时，通常使用严格大于的判断，也就是当前元素大于栈顶对应元素时才出栈更新答案。这样相同数字不会被当成更大元素。如果题目对“更大”定义很严格，就要保持这个比较规则一致。

复杂度来源

虽然代码里有 while 循环，但每个元素最多入栈一次，也最多出栈一次。也就是说，所有元素加起来的入栈和出栈次数是有限的，不会反复被处理很多次。把整个过程合在一起看，比较和弹栈的总成本是线性的，所以时间复杂度是 O(n)。