ALGORITHM SERIES | Generate an array of window maximums

calendar Oct 1, 2022 · 3 min read · algorithm English  ·
Share on: linkedin copy

Overview

Requirements

There is a integer array arr and a window of size w that slides from the leftmost to the rightmost part of the array, with the window sliding one position at a time to the right. For example, the array is [4,3,5,4,3,3,6,7], and the window size is 3.

al6-1

If the length of the array is n and the window size is w, then a total of n-w+1 window maxima are generated. Please implement a function:

  1. Input: a integer array arr with window size w
  2. output: an array res of length n-w+1, res[i] denotes the maximum value in each window state, requiring time complexity O(N*w)

Solution

al6-2

整体逻辑：

  1. 创建一个双端数组，我们需要根据不同情况从两端分别push和pop
  2. 核心就是循环这个arr，把最大的值在arr中的下标放到双端数组的最左端(对应下文程序中"for !bq.Empty() && arr[i] > arr[bq.Back().(int)] {}"的处理)
  3. 当窗口走过对应数值区域的时候，把相应的数据进行过期(对应下文程序中"if bq.Front().(int) == i-w {}")
  4. 注意，因为要输出长度为 n-w+1, 所以循环当"i >= w -1"的时候，才开始输出结果到res中

Overall logic:

  1. create a double-ended array, we need to push and pop from both ends according to different situations
  2. The core is to loop through the arr and put the largest value subscript in arr at the leftmost end of the double-ended array (corresponding to the following procedure "for !bq.Empty() && arr[i] > arr[bq. (int)] {}")
  3. expire the corresponding data when the window goes through the corresponding value area (corresponding to the following program "if bq.Front(). (int) == i-w {}")
  4. Note that since the length of the output is n-w+1, the loop starts when "i >= w -1" before outputting the result into res

Golang Implementation

 1package main
 2
 3func Getmaxwindow(arr []int, w int) (res []int) {
 4	res = []int{}
 5	// 1. create a bidirectional queue to store the result
 6	bq := newCustomQueue()
 7	// 2. for i < length(arr)
 8	for i := 0; i < len(arr); i++ {
 9		// 3. for !empty or value(in queue) > value(in bqueue), popback bqueue
10		for !bq.Empty() && arr[i] > arr[bq.Back().(int)] {
11			bq.PopBack()
12		}
13		// 4. pushback id(in queue)
14		bq.Pushback(i)
15		// 5. if bqueue's id >= i - w, expire the front value(in bqueue)
16		if bq.Front().(int) == i-w {
17			bq.PopFront()
18		}
19		// 6. record results to res slice
20		if i >= w-1 {
21			res = append(res, arr[bq.Front().(int)])
22		}
23	}
24	return res
25}

Test Cases

 1package main
 2
 3import (
 4	"github.com/stretchr/testify/assert"
 5	"testing"
 6)
 7
 8func TestGetmaxwindow(t *testing.T) {
 9	tests := []struct {
10		name string
11
12		arr []int
13		w   int
14
15		wantRes []int
16	}{
17		{
18			name:    "getmaxwindow",
19			arr:     []int{4, 3, 5, 4, 3, 3, 6, 7},
20			w:       3,
21			wantRes: []int{5, 5, 5, 4, 6, 7},
22		},
23		{
24			name:    "getmaxwindow1",
25			arr:     []int{4, 3, 5, 4, 3, 3, 6, 7},
26			w:       4,
27			wantRes: []int{5, 5, 5, 6, 7},
28		},
29		{
30			name:    "getmaxwindow2",
31			arr:     []int{4, 3, 9, 8, 3, 1, 6, 7},
32			w:       3,
33			wantRes: []int{9, 9, 9, 8, 6, 7},
34		},
35	}
36	for _, tt := range tests {
37		t.Run(tt.name, func(t *testing.T) {
38			// test case
39			res := Getmaxwindow(tt.arr, tt.w)
40			assert.Equal(t, tt.wantRes, res)
41		})
42	}
43}

Result:

 1$ go test -run ^TestSortStark$ . -v 
 2$ go test -run ^TestGetmaxwindow$ . -v
 3=== RUN   TestGetmaxwindow
 4=== RUN   TestGetmaxwindow/getmaxwindow
 5=== RUN   TestGetmaxwindow/getmaxwindow1
 6=== RUN   TestGetmaxwindow/getmaxwindow2
 7--- PASS: TestGetmaxwindow (0.00s)
 8    --- PASS: TestGetmaxwindow/getmaxwindow (0.00s)
 9    --- PASS: TestGetmaxwindow/getmaxwindow1 (0.00s)
10    --- PASS: TestGetmaxwindow/getmaxwindow2 (0.00s)
11PASS

The test is problem-free and the output is as expected.