算法：数组

一、引言 §

数组是一种线性表结构。语言中给数组分配内存时是一次性整体分配相邻的固定内存。数组对索引读友好，对扩缩容代价高。

因为数据结构比较简单，面试中数组相关题目出现会比较高频。比如排序、搜索、排列组合、集合甚至动态规划类型题型都是围绕数组来的。

二、高频面试题 §

滑动窗口的最大值

/**  
 * 长度为 K 的滑动窗口的最大值，结果为arr.length - k + 1的数组  
 * 双端队列 deque 中保存的是滑动窗口中递减的元素值  
 * @param arr  
 * @param k  
 * @return  
 */  
private static int[] maxSlide(int[] arr, int k) {  
    if(arr.length < k) return new int[0];  
    int[] ans = new int[arr.length - k + 1];  
    Deque<Integer> deque = new ArrayDeque<>();  
    for(int i = 0; i < arr.length; i++) {  
        // 双端队列中最左元素超过 K 范围时清理掉  
        if(!deque.isEmpty() && i - deque.peek() >= k) deque.remove();  
        // 双端队列右侧加入元素时把前面小于当前元素的都出队  
        while(!deque.isEmpty() && arr[deque.peekLast()] <= arr[i]) deque.removeLast();  
  
        deque.add(i);  
        // 至少 k 个元素时把双端队列最左元素加入答案中  
        if(i + 1 >= k) {  
            ans[i + 1 - k] = arr[deque.peek()];  
        }  
    }  
    return ans;  
}

三、总结 §

数组好构造，题目沟通起来简单，多种算法都可以在数组上衍生，是算法面试中高频的数据结构。