堆棧算法模闆

動态維護中位數一般都是用雙堆解決 – 同理:動态維護第K大數

81. 資料流中位數

中文

English

數字是不斷進入數組的，在每次添加一個新的數進入數組的同時傳回目前新數組的中位數。

樣例

樣例1

輸入: [1,2,3,4,5]
輸出: [1,1,2,2,3]
樣例說明：
[1] 和 [1,2] 的中位數是 1.
[1,2,3] 和 [1,2,3,4] 的中位數是 2.
[1,2,3,4,5] 的中位數是 3.
      

樣例2

輸入: [4,5,1,3,2,6,0]
輸出: [4,4,4,3,3,3,3]
樣例說明：
[4], [4,5] 和 [4,5,1] 的中位數是 4.
[4,5,1,3], [4,5,1,3,2], [4,5,1,3,2,6] 和 [4,5,1,3,2,6,0] 的中位數是 3.
      

挑戰

時間複雜度為O(nlogn)

說明

中位數的定義：

• 這裡的​

  ​中位數​

  ​不等同于數學定義裡的​

  ​中位數​

  ​。
• 中位數是排序後數組的中間值，如果有數組中有n個數，則中位數為A[(n−1)/2]A[(n-1)/2]A[(n−1)/2]。
• 比如：數組A=[1,2,3]的中位數是2，數組A=[1,19]的中位數是1。

使用雙隊列，一個minheap，一個maxheap，還是比較惡心！！！

import heapq


class Solution:
    """
    @param nums: A list of integers
    @return: the median of numbers
    """

    def medianII(self, nums):
        # write your code here
        ans = nums[:1]
        if len(nums) <= 1:
            return ans

        max_heap = []
        min_heap = [nums[0]]

        for i in range(1, len(nums)):
            m, n = len(max_heap), len(min_heap)
            if m < n:
                r = min_heap[0]
                if nums[i] > r:
                    val = heapq.heappop(min_heap)
                    heapq.heappush(max_heap, -val)
                    heapq.heappush(min_heap, nums[i])
                    ans.append(-max_heap[0])
                else:
                    heapq.heappush(max_heap, -nums[i])
                    ans.append(-max_heap[0])
            elif m == n:
                l = -max_heap[0]
                r = min_heap[0]

                if nums[i] <= l:
                    val = -heapq.heappop(max_heap)
                    heapq.heappush(min_heap, val)
                    heapq.heappush(max_heap, -nums[i])
                    ans.append(val)
                elif nums[i] <= r:
                    heapq.heappush(min_heap, nums[i])
                    ans.append(nums[i])
                else:
                    heapq.heappush(min_heap, nums[i])
                    ans.append(min_heap[0])

        return ans      

把比 median 小的放在 maxheap 裡，把比 median 大的放在 minheap 裡。median 單獨放在一個變量裡。 每次新增一個數的時候，先根據比目前的 median 大還是小丢到對應的 heap 裡。 丢完以後，再處理左右兩邊的平衡性:

1. 如果左邊太少了，就把 median 丢到左邊，從右邊拿一個最小的出來作為 median。
2. 如果右邊太少了，就把 median 丢到右邊，從左邊拿一個最大的出來作為新的 median。

import heapq


class Solution:
    """
    @param nums: A list of integers
    @return: the median of numbers
    """
    def medianII(self, nums):
        if not nums:
            return []

        self.median = nums[0]
        self.maxheap = []
        self.minheap = []

        medians = [nums[0]]
        for num in nums[1:]:
            self.add(num)
            medians.append(self.median)

        return medians

    def add(self, num):
        if num < self.median:
            heapq.heappush(self.maxheap, -num)
        else:
            heapq.heappush(self.minheap, num)

        # balanace
        if len(self.maxheap) > len(self.minheap):
            heapq.heappush(self.minheap, self.median)
            self.median = -heapq.heappop(self.maxheap)
        elif len(self.maxheap) + 1 < len(self.minheap):
            heapq.heappush(self.maxheap, -self.median)
            self.median = heapq.heappop(self.minheap)

      

python heapq子產品 删除中間某一特定參數

python内的heapq提供heappush,heappop兩個方法，然而對于 删除 中間的某個參數沒有給出相應的方法：

from heapq import heappush, heappop, _siftdown, _siftup
# heap data structure, (value, key), value is used for sorting and key used for identifying
def heapdelete(heap,i):
    nodeValue = heap[i];leafValue = heap[-1];
    if nodeValue == leafValue:
        heap.pop(-1)
    elif nodeValue <= leafValue: # similar to heappop
        heap[i], heap[-1] = heap[-1], heap[i]
        minimumValue = heap.pop(-1)
        if heap != []:
            _siftup(heap, i)
    else: # similar to heappush
        heap[i], heap[-1] = heap[-1], heap[i]
        minimumValue = heap.pop(-1)
        _siftdown(heap, 0, i)      

360. 滑動視窗的中位數

給定一個包含 n 個整數的數組，和一個大小為 k 的滑動視窗,從左到右在數組中滑動這個視窗，找到數組中每個視窗内的中位數。(如果數組個數是偶數，則在該視窗排序數字後，傳回第 N/2 個數字。)

Example 1:

Input:
[1,2,7,8,5]
3
Output:
[2,7,7]

Explanation:
At first the window is at the start of the array like this `[ | 1,2,7 | ,8,5]` , return the median `2`;
then the window move one step forward.`[1, | 2,7,8 | ,5]`, return the median `7`;
then the window move one step forward again.`[1,2, | 7,8,5 | ]`, return the median `7`;
      

Example 2:

Input:
[1,2,3,4,5,6,7]
4
Output:
[2,3,4,5]

Explanation:
At first the window is at the start of the array like this `[ | 1,2,3,4, | 5,6,7]` , return the median `2`;
then the window move one step forward.`[1,| 2,3,4,5 | 6,7]`, return the median `3`;
then the window move one step forward again.`[1,2, | 3,4,5,6 | 7 ]`, return the median `4`;
then the window move one step forward again.`[1,2,3,| 4,5,6,7 ]`, return the median `5`;
      

時間複雜度為 O(nlog(n))

使用 HashHeap。即一個 Hash + Heap。 Hash 的 key 是 Heap 裡的每個元素，值是這個元素在 Heap 中的下标。

要做這個題首先需要先做一下 Data Stream Median。這個題是隻在一個集合中增加數，不删除數，然後不斷的求中點。 Sliding Window Median，就是不斷的增加數，删除數，然後求中點。比 Data Stream Median 難的地方就在于如何支援删除數。

因為 Data Stream Median 的方法是用 兩個 Heap，一個 max heap，一個min heap。是以删除的話，就需要讓 heap 也支援删除操作。 由于 Python 的 heapq 并不支援 logn 時間内的删除操作，是以隻能自己實作一個 hash + heap 的方法。

總體時間複雜度 O(nlogk)，n是元素個數，k 是 window 的大小。      

算了，遇到這種題目就自認倒黴吧！！！      

class HashHeap:

    def __init__(self, desc=False):
        self.hash = dict()
        self.heap = []
        self.desc = desc

    @property
    def size(self):
        return len(self.heap)

    def push(self, item):
        self.heap.append(item)
        self.hash[item] = self.size - 1
        self._sift_up(self.size - 1)

    def pop(self):
        item = self.heap[0]
        self.remove(item)
        return item

    def top(self):
        return self.heap[0]

    def remove(self, item):
        if item not in self.hash:
            return

        index = self.hash[item]
        self._swap(index, self.size - 1)

        del self.hash[item]
        self.heap.pop()

        # in case of the removed item is the last item
        if index < self.size:
            self._sift_up(index)
            self._sift_down(index)

    def _smaller(self, left, right):
        return right < left if self.desc else left < right

    def _sift_up(self, index):
        while index != 0:
            parent = index // 2
            if self._smaller(self.heap[parent], self.heap[index]):
                break
            self._swap(parent, index)
            index = parent

    def _sift_down(self, index):
        if index is None:
            return
        while index * 2 < self.size:
            smallest = index
            left = index * 2
            right = index * 2 + 1

            if self._smaller(self.heap[left], self.heap[smallest]):
                smallest = left

            if right < self.size and self._smaller(self.heap[right], self.heap[smallest]):
                smallest = right

            if smallest == index:
                break

            self._swap(index, smallest)
            index = smallest

    def _swap(self, i, j):
        elem1 = self.heap[i]
        elem2 = self.heap[j]
        self.heap[i] = elem2
        self.heap[j] = elem1
        self.hash[elem1] = j
        self.hash[elem2] = i

class Solution:
    """
    @param nums: A list of integers
    @param k: An integer
    @return: The median of the element inside the window at each moving
    """
    def medianSlidingWindow(self, nums, k):
        if not nums or len(nums) < k:
            return []

        self.maxheap = HashHeap(desc=True)
        self.minheap = HashHeap()

        for i in range(0, k - 1):
            self.add((nums[i], i))

        medians = []
        for i in range(k - 1, len(nums)):
            self.add((nums[i], i))
            # print(self.maxheap.heap, self.median, self.minheap.heap)
            medians.append(self.median)
            self.remove((nums[i - k + 1], i - k + 1))
            # print(self.maxheap.heap, self.median, self.minheap.heap)

        return medians

    def add(self, item):
        if self.maxheap.size > self.minheap.size:
            self.minheap.push(item)
        else:
            self.maxheap.push(item)

        if self.maxheap.size == 0 or self.minheap.size == 0:
            return

        if self.maxheap.top() > self.minheap.top():
            self.maxheap.push(self.minheap.pop())
            self.minheap.push(self.maxheap.pop())

    def remove(self, item):
        self.maxheap.remove(item)
        self.minheap.remove(item)
        if self.maxheap.size < self.minheap.size:
            self.maxheap.push(self.minheap.pop())

    @property
    def median(self):
        return self.maxheap.top()[0]      

stack的算法      

12. 帶最小值操作的棧

實作一個棧, 支援以下操作:

• ​

  ​push(val)​

  ​ 将 val 壓入棧

• ​pop()​

  ​ 将棧頂元素彈出, 并傳回這個彈出的元素

• ​min()​

  ​ 傳回棧中元素的最小值

要求 O(1) 開銷.

樣例 2:

輸入: 
  push(1)
  min()
  push(2)
  min()
  push(3)
  min()
輸出: 
  1
  1
  1
      

注意事項

保證棧中沒有數字時不會調用 ​

​min()​

class MinStack:

    def __init__(self):
        # do intialization if necessary
        self.stack = collections.deque()

    """
    @param: number: An integer
    @return: nothing
    """
    def push(self, number):
        # write your code here
        if self.stack:
            min_val = min(self.min(), number)
        else:
            min_val = number

        self.stack.append((number, min_val))

    """
    @return: An integer
    """
    def pop(self):
        # write your code here
        return self.stack.pop()[0]

    """
    @return: An integer
    """
    def min(self):
        # write your code here
        return self.stack[-1][1]      

 這種題目還是要分析下才能快速寫出來！！！差點就被唬住了！！！

575. 字元串解碼

給出一個表達式 ​

​s​

​，此表達式包括數字，字母以及方括号。在方括号前的數字表示方括号内容的重複次數(括号内的内容可以是字元串或另一個表達式)，請将這個表達式展開成一個字元串。

輸入: S = abc3[a]
輸出: "abcaaa"
      

輸入: S = 3[2[ad]3[pf]]xyz
輸出: "adadpfpfpfadadpfpfpfadadpfpfpfxyz"
      

你可以不通過遞歸的方式完成展開嗎？

數字隻能出現在“[]”前面。

LETTERS = set("abcdefghijklmnopqrstuvwxyz")
NUMS = set("0123456789")


class Solution:
    """
    @param s: an expression includes numbers, letters and brackets
    @return: a string
    """
    def expressionExpand(self, s):
        # write your code here
        # S = 3[2[ad]3[pf]]xyz
        # = 3 f(2[ad]3[pf]) + xyz
        # =     2*f(ad) + 3*f(pf) 
        self.braces = self.calc_brace_pos(s)

        return self.helper(s, 0, len(s)-1)

    def helper(self, s, start, end):
        ans = ""
        digit = 0
        i = start
        while i <= end:
            c = s[i].lower()
            if c in NUMS:
                digit = 10*digit + (ord(c) - ord('0'))
                i += 1
            elif c in LETTERS:
                ans += s[i]
                digit = 0
                i += 1
            elif c == '[': # digit is over
                ans += self.helper(s, i+1, self.braces[i]-1)*digit
                digit = 0
                i = self.braces[i]+1

        return ans

    def calc_brace_pos(self, s):
        brace_stack = []
        ans = {}
        for i,c in enumerate(s):
            if c == '[':
                brace_stack.append(i)
            elif c == ']':
                ans[brace_stack.pop()] = i

        return ans      

遞歸的還可以寫寫，非遞歸的，狀态機太複雜了！！！

• 改成非遞歸需要棧

• 數字和字元都push

– 見到“[”push目前數字入棧

– 字元直接壓棧

• 見到“]”就pop字元直到碰到數字A

– 這些字元組成的字元串重複A次

把所有字元一個個放到 stack 裡，當碰到 "]" 的時候，就從 stack 把對應的字元串和重複次數找到，展開，然後再丢回 stack 裡，

class Solution:
    """
    @param s: an expression includes numbers, letters and brackets
    @return: a string
    """
    def expressionExpand(self, s):
        stack = []
        for c in s:
            if c == ']':
                strs = []
                while stack and stack[-1] != '[':
                    strs.append(stack.pop())

                # skip '['
                stack.pop()

                repeats = 0
                base = 1
                while stack and stack[-1].isdigit():
                    repeats += (ord(stack.pop()) - ord('0')) * base
                    base *= 10
                stack.append(''.join(reversed(strs)) * repeats)
            else:
                stack.append(c)

        return ''.join(stack)      

122. 直方圖最大矩形覆寫

給出的n個非負整數表示每個直方圖的高度，每個直方圖的寬均為1，在直方圖中找到最大的矩形面積。

Input：[2,1,5,6,2,3]
Output：10
Explanation：
The third and fourth rectangular truncated rectangle has an area of 2*5=10.
      

Input：[1,1]
Output：2
Explanation：
The first and second rectangular truncated rectangle has an area of 2*1=2.
      

經典題目：坑在前後加0      

class Solution:

    def largestRectangleArea(self, heights) -> int:

        heights = [0] + heights + [0]
        stack, max_area = [], 0

        for hi_index, height in enumerate(heights):

            while stack and height < heights[stack[-1]]:

                popped_index = stack.pop()
                lo_index = stack[-1] + 1 

                area = heights[popped_index] * (hi_index - lo_index)
                max_area = max(max_area, area)

            stack.append(hi_index)

        return max_area