对于子数组/子串问题紧密连续前缀和/滑动窗口/单调栈挖掘内在规律可以简化代码降低时空复杂度或消耗量。

二、前缀和思想子数组

抽象一下工作时长工作时长不重要重要的是两种类型用1/-1标记两种类型问题就转换成了求和为正数的最长子数组。

采用前缀和思想用map记录前面前缀和重复的只记最前面为了最长子数组为了让和为正数当sum

class

由于只有1和-1不可能前缀和出现跳跃的情况所有hashMap就可以处理。

//

new

为了最长子数组只记录最前面的前缀和。

if(!fx.containsKey(sum))

max;}

1-如何确定连续时间段两层for循环暴力确定以结果向导的前缀和确定

2-如何确定该连续时间段有效根据map中记录的前缀和确定。

2、前缀和单调栈

前缀和子数组[l

prefix[l]时则该子数组是有效数组当prefix[l1]

prefix[l2]那么l2作为左边界是无意义的毕竟l2可以则l1也可以而且还更长所以记录一下单调减序列即可。

注这里的单调栈和传统的单调栈不同不是整个数组的单调栈没有出栈操作。

再反向遍历前缀和数组和栈中元素比较不断出栈寻找prefix[r]

当r1

l2按照单调栈规则l1一定在l2上面所以出栈l1是没任何影响的。

单调栈

问题转换求和大于0的最长子数组updateHours(hours)//

记录前缀和prefix

getStack(prefix)//fmt.Println(prefix)//fmt.Println(stack)//

寻找最大子数组i

2挖掘内在规律可以简化代码降低时空复杂度或消耗量。

比如这里单调栈将前缀和简化比如这里不用TreeMap排序数值只有1/0/-1三种可能前缀和必定连续。

参考文献