栈的应用-最大宽度坡

题目：给定一个数组，每个元素只能取1或-1，求一个最长子数组的长度，满足子数组所有元素求和大于0。

输入：[1,-1,1,-1,-1,1]
输出：3
解释：求和大于0的最长子数组为[1,-1,1]，长度为3

思路：

1. 子数组的和，联想到前缀和，转换为求preSum[j]-preSum[i]>0条件下最大的j-i，这是个典型的最大宽度坡问题
2. 最大宽度坡的解法：
   2.1 初始化一个栈存元素的索引，要维持单调递减性质；从0索引开始遍历数组，将后面更小的元素的索引依次入栈；这是为了构造坡底，坡底是单调递减的。
   2.2 从末尾开始倒序遍历数组，如果数组值大于栈顶对应的值（大于坡底的值才可能成为坡顶），则计算索引与栈顶的差值，并出栈。索引与栈顶差值的最大值就是最大宽度，最大值应该放在循环判断更新。

是不是觉得很绕？用反证法解释下。
假设[i:j]为最长区间，i不是单调递减栈中的元素；那么一定存在0<=k<i，使array[k]<array[i];那么[k:j]才是最长区间，假设不成立；说明坡底一定存在于单调递减栈中。

代码：

func getLongestWidth(input []int) int {
   preSum := make([]int, len(input)+1)
   for i := 0; i < len(input); i++ {
      preSum[i+1] = preSum[i] + input[i]
   }
   stack := []int{0}
   for i := 1; i < len(preSum); i++ {
      if preSum[i] < preSum[stack[len(stack)-1]] {
         stack = append(stack, i)
      }
   }
   res := 0
   for i := len(input); i > 0; i-- {
      for len(stack) > 0 && preSum[stack[len(stack)-1]] < preSum[i] {
         res = getMax(res, i-stack[len(stack)-1])
         stack = stack[:len(stack)-1]
      }
   }
   return res
}

func getMax(a, b int) int {
   if a > b {
      return a
   }
   return b
}

有疑问加站长微信联系（非本文作者）