資料結構

1// For each day, how many days until a warmer one (0 if never).
2function dailyTemperatures(temps: number[]): number[] {
3  const answer = new Array(temps.length).fill(0);
4  const stack: number[] = [];               // days still waiting, temps falling
5  for (let i = 0; i < temps.length; i++) {
6    while (stack.length && temps[stack[stack.length - 1]] < temps[i]) {
7      const j = stack.pop()!;
8      answer[j] = i - j;
9    }
10    stack.push(i);
11  }
12  return answer;
13}
14 
15// The maximum of every window of k consecutive values.
16function slidingMax(nums: number[], k: number): number[] {
17  const deque = new Array<number>(Math.min(k, nums.length)); // circular buffer, O(k)
18  let head = 0, size = 0;
19  const at = (offset: number) => deque[(head + offset) % deque.length];
20  const maxima: number[] = [];
21  for (let i = 0; i < nums.length; i++) {
22    if (size && at(0) <= i - k) {
23      head = (head + 1) % deque.length; size--;
24    }
25    while (size && nums[at(size - 1)] <= nums[i]) {
26      size--;
27    }
28    deque[(head + size) % deque.length] = i; size++;
29    if (i >= k - 1) maxima.push(nums[at(0)]);
30  }
31  return maxima;
32}