一道OA题，单调栈，想了半天O(n)解没什么思路，求大家帮忙看看。。。

题目：
给size为n的数组。数组里的数为n的permutation，比如[4, 1, 3, 2]。假设有个子数组s，定义该子数组imbalance计算方法子数组排序后s[i]-s[i-1] > 1的总个数。要求输出所有子数组imbalance的总个数

比如[4, 1, 3, 2]
子数组 4 => 排序后4，imbalance = 0
子数组 1 => 排序后1，imbalance = 0
子数组 3 => 排序后3，imbalance = 0
子数组 2 => 排序后2，imbalance = 0
子数组 4,1 => 排序后1,4，imbalance = 1 因为 4-1=3>1
子数组 1,3 => 排序后1,3，imbalance ‍‌‍‌‌‌‌‌‍‌‌‍‌‌‌‍‍‌= 1 因为 3-1=2>1
子数组 3,2 => 排序后2,3，imbalance = 0 因为 3-2=1=1
子数组 4,1,3 => 排序后1,3,4，imbalance = 1 因为 3-1=2>1,4-3=1=1
子数组 1,3,2 => 排序后1,2,3，imbalance = 0 因为 2-1=1=1,3-2=1=1
子数组 4,1,3,2 => 排序后1,2,3,4，imbalance = 0 因为 2-1=1=1,3-2=1=1,4-3=1=1
最后输出结果为3

说是类似蠡口2104。想了半天也没什么想法。哪个高人能给个Python解的代码我吃透一下，谢谢！
这个题我吃透以后就把OA打开做了。

补充内容 (2022-09-30 03:47 +8:00):
找到个C++的答案，谁能给翻译成Python一下。C++代码看的晕，谢谢！
https://leetcode.com/playground/7bApBiDh

对于一个数n，要n对imbalance有贡献的话，那么n-1不能和n在同一个数组里。所以你要对每个n找到n-1的位置，然后看n可以在剩余的几个数组里面出贡献。

我只有c++的解法。python不够熟，就不给解法了。

求米，很缺米🤣
花了3个小时才弄懂这个题目

bydstand 发表于 2022-9-29 18:51
是的，根本不是单调栈

https://leetcode.com/playground/55hXJqEY

思考了半天，终于发现哪里不对了
你可以试一下这个例子：[3,4,6,5,1,2]。答案应该是9，但是贴的代码输出是7。输出一下每个元素的贡献，我贴在下面：
3 4
4 0
6 0
5 3
2 0
很显然，4（或者6）的贡献缺少了[4,6]这个subarray。
这个解法的问题出在，只是单纯考虑n出现在subarray中，但n-1不出现这一情况。但是这个条件是不对的，首先一个问题就是没有考虑n是否为这个subarray中最小的元素。其次就是我上面那个情况，如果有两个个元素和比它小1的元素相邻，那么这两个元素夹在中间的subarray的贡献就直接消失了。

coolwenwen 发表于 2022-9-29 20:18
对于一个数n，要n对imbalance有贡献的话，那么n-1不能和n在同一个数组里。所以你要对每个n找到n-1的位置， ...

我搜到一个C++的答案，但是我不熟C++，看不懂答案，所以上来看看有没有大神有Python的答案

coolwenwen 发表于 2022-9-29 20:18
对于一个数n，要n对imbalance有贡献的话，那么n-1不能和n在同一个数组里。所以你要对每个n找到n-1的位置， ...

老哥请问C++这两句话啥意思。
right = index < 0 ? n : maxStack[index];
ret += (((long long)(maxval)+1)*maxval)>>1;
谢谢！

DTMTouring 发表于 2022-09-29 11:38:54
老哥请问C++这两句话啥意思。
right = index < 0 ? n : maxStack;
ret += (((long long)(maxval)+1)*maxval)>>1;

Python right = n if index < 0 else maxStack[index]

补充内容 (2022-09-30 02:52 +08:00):
楼主不着急的话我明天晚上会贴一个python代码出来。

DTMTouring 发表于 2022-09-29 11:38:54
老哥请问C++这两句话啥意思。
right = index < 0 ? n : maxStack;
ret += (((long long)(maxval)+1)*maxval)>>1;

然后第二个指的是1到maxval的求和公式。>>1表示整除2

PerryLu 发表于 2022-9-29 20:50
然后第二个指的是1到maxval的求和公式。>>1表示整除2

太感谢了！！！！！！！

PerryLu 发表于 2022-9-29 20:50
然后第二个指的是1到maxval的求和公式。>>1表示整除2

老哥你看他这答案对吗
https://leetcode.com/playground/7bApBiDh

我尝试翻译成Python失败了，一会我再翻译翻译
他用index来整heap，我Python这全懵。。。。。。
Python都是heappush pop之类的

楼主可以分享一下c++的解法吗，没有搜到

Sibra_Z 发表于 2022-09-29 12:08:45
楼主可以分享一下c++的解法吗，没有搜到

我刚有个回复贴了个地址，你能受累给翻译成python吗？看那个c++代码越看越晕