0211leetcode刷題5道python

11

題目描述：
給你 n 個非負整數 a1，a2，…，an，每個數代表坐標中的一個點 (i, ai) ，在坐標內畫 n 條垂直線，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0) ，找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水，

示例：

解答：

class Solution:
    def maxArea(self, height: List[int]) -> int:
        maxv=0
        i,j=0,len(height)-1
        while i<j:
            h=min(height[i],height[j])
            maxv=max(maxv,h*(j-i))
            if height[i]<height[j]:
                i+=1
            else:
                j-=1
        return maxv

21

題目描述：
將兩個升序鏈表合并為一個新的 升序 鏈表并回傳，新鏈表是通過拼接給定的兩個鏈表的所有節點組成的，

示例：

解答：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        res = ListNode(None)
        node = res
        while l1 and l2:
            if l1.val<l2.val:
                node.next,l1 = l1,l1.next
            else:
                node.next,l2 = l2,l2.next
            node = node.next
        if l1:
            node.next = l1
        else:
            node.next = l2
        return res.next  

76

題目描述：
給你一個字串 s 、一個字串 t ，回傳 s 中涵蓋 t 所有字符的最小子串，如果 s 中不存在涵蓋 t 所有字符的子串，則回傳空字串 “” ，

示例：

解答：

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        mem=defaultdict(int)
        for char in t:
            mem[char]+=1
        t_len=len(t)

        minLeft,minRight=0,len(s)
        left=0

        for right,char in enumerate(s):
            if mem[char]>0:
                t_len-=1
            mem[char]-=1

            if t_len==0:
                while mem[s[left]]<0:
                    mem[s[left]]+=1
                    left+=1

                if right-left<minRight-minLeft:
                    minLeft,minRight=left,right

                mem[s[left]]+=1
                t_len+=1
                left+=1
        return '' if minRight==len(s) else s[minLeft:minRight+1]

84

題目描述：
給定 n 個非負整數，用來表示柱狀圖中各個柱子的高度，每個柱子彼此相鄰，且寬度為 1 ，
求在該柱狀圖中，能夠勾勒出來的矩形的最大面積，

示例:

解答：

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        '''
        超時
        res = 0
        n = len(heights)
        for i in range(n):
            left_i = i
            right_i = i
            while left_i >= 0 and heights[left_i] >= heights[i]:
                left_i -= 1
            while right_i < n and heights[right_i] >= heights[i]:
                right_i += 1
            res = max(res, (right_i - left_i - 1) * heights[i])
        return res
        '''
        #單調堆疊
        stack = []
        heights = [0] + heights + [0]
        res = 0
        for i in range(len(heights)):
            #print(stack)
            while stack and heights[stack[-1]] > heights[i]:
                tmp = stack.pop()
                res = max(res, (i - stack[-1] - 1) * heights[tmp])
            stack.append(i)
        return res

665

題目描述：
給你一個長度為 n 的整數陣列，請你判斷在 最多 改變 1 個元素的情況下，該陣列能否變成一個非遞減數列，
我們是這樣定義一個非遞減數列的： 對于陣列中所有的 i (0 <= i <= n-2)，總滿足 nums[i] <= nums[i + 1]，

示例：

解答：

class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        N = len(nums)
        count = 0
        for i in range(1, N):
            if nums[i] < nums[i - 1]:
                count += 1
                if i == 1 or nums[i] >= nums[i - 2]:
                    nums[i - 1] = nums[i]
                else:
                    nums[i] = nums[i - 1]
        return count <= 1