骨骼蠡口分类整理追加单调队列

yangzhit

LC739. Daily Temperatures (单调递减栈)，亚麻，思科，领英
739是一道G家年初老题
给出每天温度序列，想知道多少天可以等到更暖和的天气。
方法，建立一个温度递增栈。
def dailyTemperatures(self, T: List[int]) -> List[int]:
      stack=[]
      map={}
      i = 0
      while i < len(T):
         #当新温度比栈顶高，则栈顶等到了更暖和天气
         while len(stack) and T[i]>T[stack[-1]]:
            map[stack.pop()]=i
         stack.append(i)
         i = i+1
      i = 0
      result = []
      while i < len(T):
         if i in map:
            result.append(map[i]-i)
         #没等到暖和的天气，地球就流浪了
         else:
            result.append(0)
         i = i +1
      return result

beyondR

谢谢楼主，希望楼主可以继续总结。在这里我补充一下三个hard题我自己的解法和解释，各位看官要是觉得好麻烦加个米，觉得不好麻烦补充更好的写法，谢谢。

84：从某个index出发，以他为中心的的最大矩形，是找到它右边和左边第一个高度小于它的矩形为左右边界，然后相减再乘以他本身的高度
      由此可以得出，这题本质是要找到从某个index出发它左边和右边第一个高度小于它的数，因此可以得出要使用递增栈

input我们叫它array
#初始化：array结尾放0
array.append(0)
# 初始化：栈里放-1
stack = [-1]
ans = 0

for i in range(len(array)):
   # 当前index小于栈顶，说明已经不再是递增栈，我们需要pop
   while array[i] < array[stack[-1]]:
      # 依次pop出栈里大于i的元素
      height = array[stack.pop()]
      # 此时栈里元素的右边界已经确定，为i(因为i是右边第一个小于栈里元素的)
      # 因为递增，所以栈里元素的左边界就是它前面一个元素
      width = i - stack[-1] -1
      # 如果有必要的话，更新一下max
      ans = max(ans, height*width)
   # 因为我们已经pop出所有大于i的元素，现在加进去i依然可以保证是一个递增栈
   stack.append(i)
return ans

wanli

这才是值得加分的精华帖子

beyondR

本帖最后由 beyondR 于 2020-7-13 06:45 编辑

继续，42：为什么先po上一题84，因为这两题很相似，我认为需要先理解84再理解42。
和84相似，我们分析，从某个index出发，先要找到它右边和左边最高的矩形为左右边界，然后取两边更小的一个高度（木桶效应）-它本身的高度即为被困雨水的高度
由此可以得出，这题本质是要找到从某个index出发它右边和左边最高的矩形然后再找到两者相对更小的一个高度
诚然，我们依旧可以用栈来做，但是这样我们需要一个On的空间
因此，我们发现可以用双指针，再记录一下左边和右边的最大值的方法来做，这样我们的空间就优化到了01，达到最优解

依然叫input array
left, right = 0, len(array) - 1
left_max, right_max = 0, 0
ans = 0
while left < right:
   # 我们每走一步，如果applicable，先要更新left和right max
   if array[left] > left_max:
      left_max = array[left]
   if array[right] > right_max:
      right_max = array[right]
   # 然后移动双指针中较小的那一个，并且计算水位高度
   if left_max < right_max:
      ans += left_max - array[left]
      left += 1
   else:
      ans += right_max - array[right]
      right -= 1

return ans

yangzhit

LC503. Next Greater Element II, FB 亚麻
503是G家1年老题，亚麻1月老题，FB新题
给一个循环列表，找出每个元素，下一个比其大的数。
相比496，要多循环一遍，找出栈里剩下的NGN
def nextGreaterElements(self, nums: List[int]) -> List[int]:
      stack = []
      result = [-1] *len(nums)
      p=0
      while p<2*len(nums):
         while len(stack) and nums[stack[-1]] < nums[p%len(nums)]:
            result[stack.pop()]=nums[p%len(nums)]
         #第2轮不入栈
         if p<len(nums):
            stack.append(p)
         p=p+1
      return result

beyondR

最后：862 (这题写了好多，累了，orz)

def shortestSubarray(A, K):
      # 首先分析，要找一个contiguous subarray of A with sum at least K，等于要在它的prefix sum array里找到最近的两个点使其相减大于等于k
      # 也就是说对于任何一个数y，要找以它为结尾的sublist大于k，也就是要找离他最近的一个数x使其满足，y-x >= k
      # 有了这个分析以后，得到一个重要的观察，假如有 i1 < i2 而 prefix[x2] <= prefix[i1]，那我们永远不会取到i1，原因是如果对一个index满足prefix[index] - prefix[i1] >= k，那肯定也满足prefix[index] - prefix[i2] >= k，而i2比i1大，意味着i2开头的subarray比i1开头的短。
      # 因此可以得出，我们可以维护一个单调递增队列
      # 另一个重要的观察是，如果对一个index我们取了i1作为subarray的开头，那比它大的index必然不会再取i1，因为以第一个index结尾的subarray一定比以比它大的index结尾的subarray短。所以一旦用过一次，即可以pop i1出队列。


      prefix, ans = [0], len(A) + 1
      for num in A:
         prefix.append(prefix[-1] + num)


      q = collections.deque()
      for i, num in enumerate(prefix):
         # 如果prefix sum开始递减，为维护递增队列我们pop（对应观察一）
         while q and num < prefix[q[-1]]:
            q.pop()
         # 对应观察二
         while q and num - prefix[q[0]] >= K:
            ans = min(ans, i - q.popleft())
         q.append(i)

      return ans if ans < len(A) + 1 else -1

__jind

yangzhit 发表于 2020-7-12 16:55
谢谢，不确定。如果有相应解法或链接，麻烦贴出来

class Solution:
def numSubmat(self, mat) -> int:
'''
1 0 1
1 1 0
1 1 0
↓ use prefix sum by column
1 0 1
2 1 0
3 2 0
calculate the prefix sum, like:
h: [2 2 4 3 1]
index: 0 1 2 3 4
stack = [(-1, 0)]
stack.append (i, h[i]) when it is increasing.
Once you find h[3] = 3 which is not increasing,
you pop items from stack (i, h[i]),
until the item on the top of the stack has a lower height
this property means that:
# of rectangles created by the popped column =
[cur(i) - popped(i)]
* [popped(i) - stack[-1][0]]
# 左边包含 popped column 的能组成正方形的长度 * 右边... （左边和右边，包含 popped column 的所有组合）
* h[popped(i)]
'''
for row in mat:
row.append(0)
col = len(mat[0])
res = 0
h = [0 for _ in range(col)]
for row in mat:
stack = [(-1, 0)]
for i in range(col):
h[i] = h[i] + 1 if row[i] == 1 else 0 # calculate the height
while stack and len(stack) > 1 and h[stack[-1][0]] > h[i]: # and len(stack) > 1 是因为有可能 h[stack[-1][0]] 是 h[-1] 就错了
popped_i, popped_h = stack.pop()
res += (i - popped_i) * (popped_i - stack[-1][0]) * popped_h
stack.append((i, h[i]))
return res
def numSubmat___(self, mat) -> int:
'''
1 0 1
1 1 0
1 1 0
↓ use prefix sum by column
1 0 1
2 1 0
3 2 0
calculate the prefix sum, like:
h: [2 2 4 3 1]
index: 0 1 2 3 4
# of rectangles created by the cur column =
(the index of the cur column - the index of the previous column with lower height)
* the height of cur column
+ the submatries owing to the previous column with lower height
we store the # of rectangle with the index, like: (index, # of rectangle of the cur column)
Once you find h[3] = 3 which is not increasing,
you pop items from stack (i, previous rectangle),
until the item on the top of the stack has a lower height
'''
col = len(mat[0])
res = 0
h = [0 for _ in range(col)]
for row in mat:
stack = [(-1, 0)]
for i in range(col):
h[i] = h[i] + 1 if row[i] == 1 else 0 # calculate the height
while stack and len(stack) > 1 and h[stack[-1][0]] > h[i]:
stack.pop()
# the rectangles created by cur column
width = i - stack[-1][0]
plus = stack[-1][1]
cur = width*h[i] + plus
stack.append((i, cur))
res += cur
print(h)
return res

复制代码

yangzhit

beyondR 发表于 2020-7-13 07:25
最后：862 (这题写了好多，累了，orz)

def shortestSubarray(A, K):

感谢题解和详细的注释，我根据这个思路写了自己的代码。

def shortestSubarray(self, A: List[int], K: int) -> int:
      sum = [0]
      for a in A:
         sum.append(sum[-1]+a)
      result = len(sum)
      stack=[]
      for i in range(len(sum)):
         while stack and sum[i]<=sum[stack[-1]]:
            stack.pop()
         while stack and sum[i]-sum[stack[0]]>=K:
            result = min(result, i-stack.pop(0))
         stack.append(i)
      if result == len(sum):
         return -1
      return result

跟一个实例分析
A=[84,-37,32,40,95]
K=167
Sum 区间栈
0                [0]
84    [0,0] [0,84]
47    [0,1] [0,47]    如果某个sum-84符合>167，sum-47肯定符合，而-47更优。第一个while
79    [0,2] [0,47,79]  如果sum-47符合>167，sum-79不一定。79-47不>=167
119 [0,3] [0,47,79,119]
214 [0,4] [0,47,79,119],214 如果sum1-0符合,则sum2/3/4-0不是最优解。所以0可以删除，第二个while

yangzhit

42. Trapping Rain Water
根据下面这个帖子，写了一个Python版本
https://www.cnblogs.com/grandyang/p/4402392.html
跟前面几题不一样的是，用到栈里两个数，一个作为左边的高，一个作为底。
栈是一个递减栈，这样才能形成一个坑。算坑里的水，是一个个底往上算。
def trap(self, height: List[int]) -> int:
      s=[]
      r=0
      for i in range(len(height)):
         while s and height[i]>height[s[-1]]:
            t = s.pop()
            if s:
                  r = r + (min(height[i], height[s[-1]]) - height[t]) * (i-s[-1]-1)
         s.append(i)
      return r

min(height[i], height[s[-1]]) - height[t] 两边高取小，再把前面算过的底去掉
i-s[-1]-1 两边的距离减一，紧挨着盛不了水

yangzhit

84. Largest Rectangle in Histogram
这道题，根据下面帖子写了Python版
https://www.cnblogs.com/love-yh/p/7182920.html
主要是分两种情况，1. 如果栈不空，部分算面积 2. 如果栈空，全长算面积
def largestRectangleArea(self, heights: List[int]) -> int:
      max = 0
      stack = []
      heights.append(-1)
      for i in range(0, len(heights)):
         while stack and heights[i] < heights[stack[-1]]:
            last = stack.pop()
            if stack and heights[last] * (i-stack[-1]-1)>max:
                  max = heights[last] * (i-stack[-1]-1) #部分
            elif stack ==0 and heights[last] * i>max:
                  max = heights[last] * i #全长
         stack.append(i)
      return max

骨骼蠡口分类整理追加单调队列

评分

评分

评分

评分

本帖子中包含更多资源

浏览过的版块