LeetCode第239题 – 滑动窗口最大值

785 views

题目

解答

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null) {
            return null;
        }

        LinkedList<Integer> window = new LinkedList<>();
        List<Integer> arr = new ArrayList<>(k);

        int right = 0;

        while (right < nums.length) {
            int newValue = nums[right];
            while (!window.isEmpty() && window.peekLast() < newValue) {
                window.removeLast();
            }

            window.addLast(newValue);

            ++right;

            if (right >= k) {
                arr.add(window.peekFirst());

                if (window.peekFirst() == nums[right - k]) {
                    window.removeFirst();
                }
            }
        }

        int[] values = new int[arr.size()];
        for (int i = 0; i < arr.size(); ++i) {
            values[i] = arr.get(i);
        }
        return values;
    }
}

要点

准备的用例,如下

@Before
public void before() {
    t = new Solution();
}

@Test
public void test001() {
    assertTrue(Arrays.equals(new int[] { 3, 3, 5, 5, 6, 7 },
            t.maxSlidingWindow(new int[] { 1, 3, -1, -3, 5, 3, 6, 7 }, 3)));
}

@Test
public void test002() {
    assertTrue(Arrays.equals(new int[] { 1 }, t.maxSlidingWindow(new int[] { 1 }, 1)));
}

@Test
public void test003() {
    assertTrue(Arrays.equals(new int[] { 1, -1 }, t.maxSlidingWindow(new int[] { 1, -1 }, 1)));
}

@Test
public void test004() {
    assertTrue(Arrays.equals(new int[] { 11 }, t.maxSlidingWindow(new int[] { 9, 11 }, 2)));
}

@Test
public void test005() {
    assertTrue(Arrays.equals(new int[] { 4 }, t.maxSlidingWindow(new int[] { 4, -2 }, 2)));
}

如下两篇文章对于滑动窗口算法的介绍通俗易懂,值得反复阅读。



若非注明,均为原创,欢迎转载,转载请注明来源:LeetCode第239题 – 滑动窗口最大值

关于 JackieAtHome

基层程序员,八年之后重新启航

此条目发表在 Java, LeetCode 分类目录。将固定链接加入收藏夹。