764. 最大加号标志

764. 最大加号标志

class Solution:
    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:
        dp = [[[0, 0, 0, 0] for i in range(n)] for j in range(n)]
        mines = set(list(map(tuple, mines)))
        for i in range(n):
            for j in range(n):
                if (i, j) in mines:
                    dp[i][j][0] = 0
                    dp[i][j][1] = 0
                else:
                    dp[i][j][0] = dp[i - 1][j][0] + 1 if i - 1 >= 0 else 1
                    dp[i][j][1] = dp[i][j - 1][1] + 1 if j - 1 >= 0 else 1
        for i in range(n - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if (i, j) in mines:
                    dp[i][j][2] = 0
                    dp[i][j][3] = 0
                else:
                    dp[i][j][2] = dp[i + 1][j][2] + 1 if i + 1 < n else 1
                    dp[i][j][3] = dp[i][j + 1][3] + 1 if j + 1 < n else 1
        ans = 0
        for i in range(n):
            for j in range(n):
                ans = max(ans, min(dp[i][j]))
        return ans

1944. 队列中可以看到的人数

1944. 队列中可以看到的人数

class Solution:
    def canSeePersonsCount(self, heights: List[int]) -> List[int]:
        stack = []
        ans = [0 for i in range(len(heights))]
        for i in range(len(heights) - 1, -1, -1):
            while stack and heights[i] > stack[-1]:
                ans[i] += 1
                stack.pop()
            if stack:
                ans[i] += 1
            stack.append(heights[i])
        return ans

2439. 最小化数组中的最大值

2439. 最小化数组中的最大值

使用二分法检查数

class Solution:
    def minimizeArrayValue(self, nums: List[int]) -> int:
        right = 10 ** 9
        left = 0
        while left < right:
            mid = left + (right - left) // 2
            if self.check(mid, nums):
                right = mid
            else:
                left = mid + 1
        return left

    def check(self, k, nums):
        num = 0
        for i in range(len(nums)):
            if nums[i] < k:
                num += k - nums[i]
            else:
                if num < (nums[i] - k):
                    return False
                else:
                    num -= nums[i] - k
        return True

LCR 009. 乘积小于 K 的子数组

LCR 009. 乘积小于 K 的子数组

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        cnt = 0
        mul = 1
        p0 = 0
        for p1 in range(len(nums)):
            mul *= nums[p1]
            while p0 <= p1 and mul >= k:
                mul //= nums[p0]
                p0 += 1
            cnt += p1 - p0 + 1
        return cnt

966. 元音拼写检查器

966. 元音拼写检查器

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        words_set = set(wordlist)
        words_lower = {wordlist[i].lower(): wordlist[i] for i in range(len(wordlist) - 1, -1, -1)}
        words_vow = {"".join([c if c not in 'aeiou' else '*' for c in wordlist[i].lower()]): wordlist[i] for i in
                     range(len(wordlist) - 1, -1, -1)}
        ans = []
        for word in queries:
            if word in words_set:
                ans.append(word)
                continue
            word_lower = word.lower()
            if word_lower in words_lower:
                ans.append(words_lower[word_lower])
                continue
            word_vow = "".join([c if c not in 'aeiou' else '*' for c in word_lower])
            if word_vow in words_vow:
                ans.append(words_vow[word_vow])
                continue
            ans.append('')
        return ans