栈2

继续刷栈！！！

leetcode 496 下一个更大的元素I

维护一个栈，当下一个元素比栈顶大时，出栈直到栈顶大于该元素。

不够 pythonic解法：

class Solution(object):
    def nextGreaterElement(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        if not nums1 or not nums2:
            return
        stack = []
        hashMap = {}
        result = []
        for num in nums2:
            if not stack:
                stack.append(num)
                continue
            while stack and num > stack[-1]:
                hashMap[stack.pop()] = num
            stack.append(num)

        for num in nums1:
            if num in hashMap:
                result.append(hashMap[num])
            else:
                result.append(-1)

        return result

pythonic解法：

class Solution(object):
    def nextGreaterElement(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        if not nums1 or not nums2:
            return
        stack = []
        hashMap = {}
        result = []
        for num in nums2:
            while stack and num > stack[-1]:
                hashMap[stack.pop()] = num
            stack.append(num)

        return [hashMap.get(i, -1) for i in nums1]

leetcode 503 下一个更大的元素II

返回数组格式固定。维护一个栈，不放数字放下标，找到下标后放到待返回的数组！

class Solution(object):
    def nextGreaterElements(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        double_nums = nums + nums
        stack = []
        result = [-1] * len(nums)
        for index, num in enumerate(double_nums):
            while stack and num > nums[stack[-1]]:
                result[stack.pop()] = num
            if index < len(nums):
                stack.append(index)
        return result

leetcode 682 棒球比赛

这题就比较简单了，不过我好像写复杂了，不需要每步计算ans，直接最后求栈的和就可以了。好像动态规划也行

class Solution(object):
    def calPoints(self, ops):
        """
        :type ops: List[str]
        :rtype: int
        """
        ans = 0
        stack = []
        for i in ops:
            if i.isdigit() or i.startswith("-"):
                ans += int(i)
                stack.append(int(i))
            elif i == "C":
                ans -= stack[-1]
                stack.pop()
            elif i == "D":
                t = stack[-1] * 2
                ans += t
                stack.append(t)
            elif i == "+":
                t = stack[-1] + stack[-2]
                ans += t
                stack.append(t)
        return ans

class Solution(object):
    def calPoints(self, ops):
        """
        :type ops: List[str]
        :rtype: int
        """
        stack = []
        for i in ops:
            if i.isdigit() or i.startswith("-"):
                stack.append(int(i))
            elif i == "C":
                stack.pop()
            elif i == "D":
                t = stack[-1] * 2
                stack.append(t)
            elif i == "+":
                t = stack[-1] + stack[-2]
                stack.append(t)
        return sum(stack)

leetcode 636 线程独占的时间

老思路，先生成结果，然后将多运行的时间减去。

class Solution(object):
    def exclusiveTime(self, n, logs):
        """
        :type n: int
        :type logs: List[str]
        :rtype: List[int]
        """
        logsHelp = [(int(i.split(':')[0]), i.split(':')[1], int(i.split(':')[2])) for i in logs]
        result = [0] * n
        stack = []
        for log in logsHelp:
            if log[1] == "start":
                stack.append(log)
            else:
                t = stack.pop()
                time = log[2] - t[2] + 1
                n = t[0]
                result[n] += time
                if stack:
                    result[stack[-1][0]] -= time
        return result