1. 滑动窗口最大值 🌟🌟🌟

2. 用栈实现队列 🌟

3. 直线上最多的点数 🌟🌟🌟

🌟 每日一练刷题专栏 🌟

Golang每日一练专栏

Python每日一练专栏

C/C++每日一练专栏

Java每日一练专栏

1. 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
1  [3  -1  -3] 5  3  6  7       3
1   3 [-1  -3  5] 3  6  7       5
1   3  -1 [-3  5  3] 6  7       5
1   3  -1  -3 [5  3  6] 7       6
1   3  -1  -3  5 [3  6  7]      7

示例 2：

输入：nums = [1], k = 1
输出：[1]

示例 3：

输入：nums = [1,-1], k = 1
输出：[1,-1]

示例 4：

输入：nums = [9,11], k = 2
输出：[11]

示例 5：

输入：nums = [4,-2], k = 2
输出：[4]

提示：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

出处：

https://edu.csdn.net/practice/26377425

代码：

class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        if len(nums) == 0:
            return []
        if k == 1:
            return nums
        res = []
        res.append(max(nums[:k]))
        for i in range(1, len(nums) - k + 1):
            m = max(nums[i : i + k])
            res.append(m)
        return res

if __name__ == '__main__':
    s = Solution()
    nums = [1,3,-1,-3,5,3,6,7]; k = 3
    print(s.maxSlidingWindow(nums, k))

输出：

[3, 3, 5, 5, 6, 7]

2. 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

进阶：

你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

示例：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释： 
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1] 
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) 
myQueue.peek();  // return 1 
myQueue.pop();   // return 1, queue is [2] 
myQueue.empty(); // return false

提示：

1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的（例如，一个空的队列不会调用 pop 或者 peek 操作）

出处：

https://edu.csdn.net/practice/26377426

代码：

class MyQueue:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.stack_push = []
        self.stack_pop = []
    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        while self.stack_pop:
            self.stack_push.append(self.stack_pop.pop())
        self.stack_push.append(x)
    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        if self.empty():
            return None
        else:
            while self.stack_push:
                self.stack_pop.append(self.stack_push.pop())
            return self.stack_pop.pop()
    def peek(self) -> int:
        """
        Get the front element.
        """
        if self.empty():
            return None
        elif not self.stack_pop:
            return self.stack_push[0]
        else:
            return self.stack_pop[-1]
    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return not (self.stack_push or self.stack_pop)

# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

myQueue = MyQueue()
myQueue.push(1)  # queue is: [1]
myQueue.push(2)  # queue is: [1, 2] (leftmost is front of the queue)
print(myQueue.peek())   # return 1
print(myQueue.pop())    # return 1, queue is [2]
print(myQueue.empty())  # return false

输出：

1
1
False

3. 直线上最多的点数

给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

示例 1：

输入：points = [[1,1],[2,2],[3,3]]
输出：3

示例 2：

输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出：4

提示：

1 <= points.length <= 300
points[i].length == 2
-104 <= xi, yi <= 104
points 中的所有点 互不相同

出处：

https://edu.csdn.net/practice/26377427

代码：

from typing import List

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        if len(points) <= 2:
            return len(points)
        maxNum = 0
        for i in range(len(points)):
            maxNum = max(maxNum, self.find(points[i], points[:i] + points[i + 1 :]))
        return maxNum + 1
    def find(self, point, pointList):
        memories = {}
        count = 0
        inf = float("inf")
        for curPoint in pointList:
            if curPoint[1] == point[1] and curPoint[0] != point[0]:
                memories[inf] = memories.get(inf, 0) + 1
            elif curPoint[1] == point[1] and curPoint[0] == point[0]:
                count += 1
            else:
                slope = (curPoint[0] - point[0]) / (curPoint[1] - point[1])
                memories[slope] = memories.get(slope, 0) + 1
        if memories:
            return count + max(memories.values())
        else:
            return count

if __name__ == '__main__':
    s = Solution()
    null = None
    points = [[1,1],[2,2],[3,3]]
    print(s.maxPoints(points))
    points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
    print(s.maxPoints(points))

输出：

3
4