栈、单调队列与堆

from collections import deque


def max_sliding_window(nums: list[int], k: int) -> list[int]:
    """Maximum of every length-k window (LC 239)."""
    dq: deque[int] = deque()  # indexes in the window, values decreasing front to back
    res = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()  # smaller values before x can never be a maximum again
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()  # the front slid out of the window
        if i >= k - 1:
            res.append(nums[dq[0]])
    return res

// Maximum of every length-k window (LC 239).
vector<int> maxSlidingWindow(const vector<int>& nums, int k) {
    deque<int> dq;  // indexes in the window, values decreasing front to back
    vector<int> res;
    for (int i = 0; i < (int)nums.size(); i++) {
        while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back();  // they can never be a maximum again
        dq.push_back(i);
        if (dq.front() <= i - k) dq.pop_front();  // the front slid out of the window
        if (i >= k - 1) res.push_back(nums[dq.front()]);
    }
    return res;
}

class Solution {
    // Maximum of every length-k window (LC 239).
    int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> dq = new ArrayDeque<>(); // indexes in the window, values decreasing front to back
        int[] res = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++) {
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast(); // they can never be a maximum again
            dq.offerLast(i);
            if (dq.peekFirst() <= i - k) dq.pollFirst(); // the front slid out of the window
            if (i >= k - 1) res[i - k + 1] = nums[dq.peekFirst()];
        }
        return res;
    }
}

// maxSlidingWindow returns the maximum of every length-k window (LC 239).
func maxSlidingWindow(nums []int, k int) []int {
	var dq []int // indexes in the window, values decreasing front to back
	var res []int
	for i, x := range nums {
		for len(dq) > 0 && nums[dq[len(dq)-1]] <= x {
			dq = dq[:len(dq)-1] // they can never be a maximum again
		}
		dq = append(dq, i)
		if dq[0] <= i-k {
			dq = dq[1:] // the front slid out of the window
		}
		if i >= k-1 {
			res = append(res, nums[dq[0]])
		}
	}
	return res
}

import heapq


def kth_largest(nums: list[int], k: int) -> int:
    """The k-th largest value (LC 215), with a size-k min-heap."""
    heap: list[int] = []  # the k largest so far; heap[0] is the smallest of them
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)  # x beats the weakest of the top k
    return heap[0]

// The k-th largest value (LC 215), with a size-k min-heap.
int kthLargest(const vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> heap;  // the k largest so far; top is the smallest
    for (int x : nums) {
        if ((int)heap.size() < k) heap.push(x);
        else if (x > heap.top()) {
            heap.pop();  // x beats the weakest of the top k
            heap.push(x);
        }
    }
    return heap.top();
}

class Solution {
    // The k-th largest value (LC 215), with a size-k min-heap.
    int kthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(); // the k largest so far; peek() is the smallest
        for (int x : nums) {
            if (heap.size() < k) heap.offer(x);
            else if (x > heap.peek()) {
                heap.poll(); // x beats the weakest of the top k
                heap.offer(x);
            }
        }
        return heap.peek();
    }
}

import "container/heap"

// minHeap is a min-heap of ints for container/heap.
type minHeap []int

func (h minHeap) Len() int           { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h minHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *minHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

// kthLargest returns the k-th largest value (LC 215), with a size-k min-heap.
func kthLargest(nums []int, k int) int {
	h := &minHeap{} // the k largest so far; (*h)[0] is the smallest
	for _, x := range nums {
		if h.Len() < k {
			heap.Push(h, x)
		} else if x > (*h)[0] {
			(*h)[0] = x // x beats the weakest of the top k
			heap.Fix(h, 0)
		}
	}
	return (*h)[0]
}

def calculate(s: str) -> int:
    """+ - * / over non-negative integers, no parentheses (LC 227); / truncates toward zero."""
    stack: list[int] = []  # signed terms to add up; * and / fold into the last one
    num, op = 0, "+"  # op: the operator before num
    for i, c in enumerate(s):
        if c.isdigit():
            num = num * 10 + int(c)
        if (not c.isdigit() and c != " ") or i == len(s) - 1:  # an operator or the end closes num
            if op == "+":
                stack.append(num)
            elif op == "-":
                stack.append(-num)
            elif op == "*":
                stack.append(stack.pop() * num)
            else:
                top = stack.pop()
                stack.append(abs(top) // num * (1 if top >= 0 else -1))  # truncate toward zero
            op, num = c, 0
    return sum(stack)

// + - * / over non-negative integers, no parentheses (LC 227); / truncates toward zero.
long long calculate(const string& s) {
    vector<long long> stack;  // signed terms to add up; * and / fold into the last one
    long long num = 0;
    char op = '+';  // the operator before num
    for (size_t i = 0; i < s.size(); i++) {
        char c = s[i];
        if (isdigit(c)) num = num * 10 + (c - '0');
        if ((!isdigit(c) && c != ' ') || i == s.size() - 1) {  // an operator or the end closes num
            if (op == '+') stack.push_back(num);
            else if (op == '-') stack.push_back(-num);
            else if (op == '*') stack.back() *= num;
            else stack.back() /= num;  // C++ division truncates toward zero
            op = c;
            num = 0;
        }
    }
    return accumulate(stack.begin(), stack.end(), 0LL);
}

class Solution {
    // + - * / over non-negative integers, no parentheses (LC 227); / truncates toward zero.
    long calculate(String s) {
        Deque<Long> stack = new ArrayDeque<>(); // signed terms to add up; * and / fold into the last one
        long num = 0;
        char op = '+'; // the operator before num
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) num = num * 10 + (c - '0');
            if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) { // an operator or the end closes num
                if (op == '+') stack.push(num);
                else if (op == '-') stack.push(-num);
                else if (op == '*') stack.push(stack.pop() * num);
                else stack.push(stack.pop() / num); // Java division truncates toward zero
                op = c;
                num = 0;
            }
        }
        long total = 0;
        for (long term : stack) total += term;
        return total;
    }
}

// calculate evaluates + - * / over non-negative integers, no parentheses (LC 227).
func calculate(s string) int {
	var stack []int // signed terms to add up; * and / fold into the last one
	num, op := 0, byte('+') // op: the operator before num
	for i := 0; i < len(s); i++ {
		c := s[i]
		digit := c >= '0' && c <= '9'
		if digit {
			num = num*10 + int(c-'0')
		}
		if (!digit && c != ' ') || i == len(s)-1 { // an operator or the end closes num
			switch op {
			case '+':
				stack = append(stack, num)
			case '-':
				stack = append(stack, -num)
			case '*':
				stack[len(stack)-1] *= num
			default:
				stack[len(stack)-1] /= num // Go division truncates toward zero
			}
			op, num = c, 0
		}
	}
	total := 0
	for _, term := range stack {
		total += term
	}
	return total
}