Back to Leetcode

Readme

Stack/3676.Count-Bowl-Subarrays/Readme.md

latest796 B
Original Source

3676.Count-Bowl-Subarrays

非常有趣的题目。

我们很容易想到,对于每个nums[i]考虑其作为一个端点时,另一个端点应该在哪些位置。我们不妨认为nums[i]是左边且较低的端点,那么我们很容易找到对应的next greater element,比如说j,这是下一个可以作为右端点的位置,而这恰恰也是它所对应的唯一的右端点。如果再往右寻找右端点,那么j处在bowl内部就高于了左端点,不符合条件。

于是我们就可以得出结论,对于每个nums[i],只有唯一的next greater element可以配对为右边且更高的端点。同理,对于每个nums[i],只有唯一的prev greater element可以配对为左边且更高的端点。这样我们就枚举除了所有的bowl的形状。