数据结构与算法学习笔记（训练营一）---单调栈和滑动窗口

滑动窗口是什么？

  • 滑动窗口是一种想象出来的数据结构。
  • 滑动窗口有左边界L和有边界R。
  • 在数组或者字符串或者一个序列上，记为S，窗口就是S[L..R]这一部分。
  • L往右滑意味着一个样本出了窗口，R往右滑意味着一个样本进了窗口
    L和R都只能往右滑。

滑动窗口能做什么？

  • 滑动窗口、首尾指针等技巧，说白了是一种求解问题的流程设计。

滑动内最大值和最小值的更新结构

  • 窗口不管L还是R滑动之后，都会让窗口呈现新状况，
  • 如何能够更快的得到窗口当前状况下的最大值和最小值？
  • 最好平均下来复杂度能做到O(1)
  • 利用单调双端队列！

例题

  • 假设一个固定大小为W的窗口，依次划过arr，返回每一次滑出状况的最大值。例如，arr = [4,3,5,4,3,3,6,7], W = 3，返回：[5,5,5,4,6,7]
/**
 * 求滑动窗口的最大值和最小值流程（L,R分别是窗口的边界）
 * <p>
 * 求窗口内最大值（利用双端队列实现）
 * 1.滑动窗口R向右移动时,窗口增加,如果此时队列为空那么直接从尾部加入队列，如果队列不为空
 * 那么比较队列尾部元素和当前元素大小，如果当前元素比队列尾部元素小那么从尾部加入当前元素，
 * 如果当前元素比队列尾部元素大于等于那么，那么弹出队列尾部元素，继续比较当前元素和队列尾部元素，
 * 知道队列尾部元素大于当前元素。此时队头元素就是此时形成的窗口的最大值。
 * 2.滑动窗口L向右移动时，窗口减小。比较此时移除窗口的元素是否是队列中的元素如不不是，什么也不用做
 * 如果窗口移出元素刚好等于队列头部元素，那么从队列头部移出改元素，此时队列中的新头部元素就是此时
 * 窗口的最大值。
 * <p>
 * 假设一个固定大小为W的窗口，依次划过arr，
 * 返回每一次滑出状况的最大值
 * 例如，arr = [4,3,5,4,3,3,6,7], W = 3
 * 返回：[5,5,5,4,6,7]
 */
public class SlidingWindow {

    //形成一个窗口为3的滑动窗口，每次求出最大值，最后返回
    public static int[] slidingWindowsMax(int[] arr, int w) {
        if (arr == null || arr.length == 0 || w <= 0 || arr.length - w < -1) {
            return null;
        }
        int len = arr.length;
        int[] res = new int[len - w +1];
        int index = 0;
        LinkedList<Integer> queueMax = new LinkedList<>();
        for (int R = 0; R < len; R++) {
            // 加入双端队列
            while (!queueMax.isEmpty()
                    && arr[R] >= arr[queueMax.peekLast()]) {
                queueMax.pollLast();
            }
            queueMax.offerLast(R);

            if((R - w >=0) &&(R - w) == queueMax.peekFirst()){
                queueMax.pollFirst();
            }
            if(R - w >= -1){
                // 形成了w窗口，取出最大值
                res[index++] = arr[queueMax.peekFirst()];
            }
        }

        return res;
    }

    public static void main(String[] args) {
        // [5,5,5,4,6,7]
        int[] arr = new int[]{4,2,3,3,5,1,1,1,1,8};
        int w = 3;
        int[] ints = slidingWindowsMax(arr, w);
        for(int i : ints){
            System.out.print(i+" ");
        }

    }
}
  • 滑动窗口内最小值：
    1.滑动窗口R向右移动，如果队列为空，直接加入队列，否则比较队尾元素和当前元素，若当前元素大于等于队尾元素则加入，否则弹出队尾元素再次进行比较直到当前元素大于等于队尾元素，加入当前元素。
    2.滑动窗口L向右移动，若当前元素不等于队列中的队头元素那么不用管，此时队列中的队头元素就是此时窗口的最小值。若当前元素等于队列头部元素则删除队头元素，此时队列的新头就是此时滑动窗口的最小值。
  • 给定一个整型数组arr，和一个整数num
    某个arr中的子数组sub，如果想达标，必须满足：
    sub中最大值 – sub中最小值 <= num，
    返回arr中达标子数组的数量
/**
 * 给定一个整型数组arr，和一个整数num
 * 某个arr中的子数组sub，如果想达标，必须满足：
 * sub中最大值 – sub中最小值 <= num，
 * 返回arr中达标子数组的数量
 */
public class SubArray {
    // 首先如果在L -> R 上是达标子数组，那么在L -> R 内的的子数组都是达标的，因为在这个
    // 范围上最大值，只可能比L -> R上的小，最小值只可能比L -> R上的大，所以还是满足达标子数组的要求
    // 如果在L ->R上不满足，那么在大于L -> R的范围上也不会存在达标的子数组
    // 因为最大值只可可能更大，最小值只可能更小，那么本来就不满足，现在差距跟大了，一定不满足
    // 现在可以这样做以数组汇总每个位置为开头，一直滑动R形成一个窗口找出以当前位置为头的最大的
    // 达标的子数组，然后 R - L + 1就是以当前位置开头的达标子数组的所有。
    // 然后在换开头，遍历完所有的位置结果就出来了
    public static int subArray(int[] arr,int num){
        if(arr == null || arr.length == 0){
            return 0;
        }

        // 窗口最大值
        LinkedList<Integer> maxQ = new LinkedList<>();
        // 窗口最小值
        LinkedList<Integer> minQ = new LinkedList<>();
        int len = arr.length;
        int L = 0;
        int R = 0;
        int res = 0;
        while (L < len){
            while (!maxQ.isEmpty() && arr[R] >= arr[maxQ.peekLast()]){
                maxQ.pollLast();
            }
            maxQ.offerLast(R);

            while (!minQ.isEmpty() && arr[R] <= arr[minQ.peekLast()]){
                minQ.pollLast();
            }
            minQ.offerLast(R);
            // 如果此时最大值和最小值不达标，开始结算
            if(arr[maxQ.peekFirst()] - arr[minQ.peekFirst()]> num){
                res += R - L;
            }else{
                if(R == len - 1){
                    res += R - L + 1;
                    L ++;
                }else {
                    R ++;
                }
                continue;
            }
            // 结算完以后让L 前进一步,并且调整 最大最小队列
            if(maxQ.peekFirst() == L){
                maxQ.pollFirst();
            }
            if(minQ.peekFirst() == L){
                minQ.pollFirst();
            }

            L ++;

        }
        return res;
    }

    public static int subArray2(int[] arr,int num){
        if(arr == null || arr.length == 0){
            return 0;
        }

        // 窗口最大值
        LinkedList<Integer> maxQ = new LinkedList<>();
        // 窗口最小值
        LinkedList<Integer> minQ = new LinkedList<>();
        int len = arr.length;
        int L = 0;
        int R = 0;
        int res = 0;
        while (L < len){
            // 每个L位置尝试最大子数组
            while (R < len){
                // R不断扩大直到破坏子数组条件
                while (!maxQ.isEmpty() && arr[R] >= arr[maxQ.peekLast()]){
                    maxQ.pollLast();
                }
                maxQ.offerLast(R);

                while (!minQ.isEmpty() && arr[R] <= arr[minQ.peekLast()]){
                    minQ.pollLast();
                }
                minQ.offerLast(R);
                if(arr[maxQ.peekFirst()] - arr[minQ.peekFirst()]> num){
                    // 跳出R向右扩循环
                    break;
                }
                    R ++;
            }
            res += R - L;
            // 结算完以后让L 前进一步,并且调整 最大最小队列
            if(maxQ.peekFirst() == L){
                maxQ.pollFirst();
            }
            if(minQ.peekFirst() == L){
                minQ.pollFirst();
            }
            L ++;
        }
        return res;
    }
}

单调栈是什么？

一种特别设计的栈结构，为了解决如下的问题：
给定一个可能含有重复值的数组arr，i位置的数一定存在如下两个信息
1）arr[i]的左侧离i最近并且小于(或者大于)arr[i]的数在哪？
2）arr[i]的右侧离i最近并且小于(或者大于)arr[i]的数在哪？
如果想得到arr中所有位置的两个信息，怎么能让得到信息的过程尽量快。
那么到底怎么设计呢？

/**
 * 单调栈
 * 一种特别设计的栈结构，为了解决如下的问题：
 * 给定一个可能含有重复值的数组arr，i位置的数一定存在如下两个信息
 * 1）arr[i]的左侧离i最近并且小于(或者大于)arr[i]的数在哪？
 * 2）arr[i]的右侧离i最近并且小于(或者大于)arr[i]的数在哪？
 * 如果想得到arr中所有位置的两个信息，怎么能让得到信息的过程尽量快。
 */
public class MonotonousStack {

    // 数组中无重复元素
    public static int[][] monotonousStack(int[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }

        int len = arr.length;
        // 准备一个栈,存放元素下标
        Stack<Integer> stack = new Stack<>();
        // 返回数组,每个元素占据一行，每一行有两列，第一列表示离当前元素最近的左边小的元素
        // 第二列表示离当前元素最近的右边小的元素
        int[][] res = new int[len][2];
        int index = 0;
        while (index < len) {
            while (!stack.isEmpty() && arr[stack.peek()] > arr[index]){
                // 收集答案，弹出栈顶元素 pop 是元素的下标
                int pop = stack.pop();
                int temp = stack.isEmpty() ? -1:stack.peek();
                res[pop][0] = temp;
                res[pop][1] = index;
            }
            stack.push(index++);

        }
        while (!stack.isEmpty()) {
            int cur = stack.pop();
            int temp = stack.isEmpty() ? -1:stack.peek();
            // 没有右边最近小的元素用-1代替
            res[cur][1] = -1;
            res[cur][0] = temp;
        }

        return res;
    }

    // 数组中有重复元素
    public static int[][] monotonousStack2(int[] arr){
        if (arr == null || arr.length == 0) {
            return null;
        }

        int len = arr.length;
        Stack<List<Integer>> stack = new Stack<>();
        int[][] res = new int[len][2];
        int index = 0;
        while (index < len){
            while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[index]){
                List<Integer> pop = stack.pop();
                for(Integer item : pop){
                    int temp = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size()-1);
                    res[item][0] = temp;
                    res[item][1] = index;
                }

            }
            if(!stack.isEmpty() && arr[stack.peek().get(0)] == arr[index]){
                stack.peek().add(index);
            }else {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(index);
                stack.push(list);
            }
            index ++;
        }

        while (!stack.isEmpty()) {
            List<Integer> list = stack.pop();
            for(Integer item : list){
                int temp = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size()-1);
                res[item][0] = temp;
                res[item][1] = -1;
            }
        }

        return res;

    }
 
}
  • 给定一个只包含正数的数组arr，arr中任何一个子数组sub，
    一定都可以算出(sub累加和 )* (sub中的最小值)是什么，
    那么所有子数组中，这个值最大是多少？

滑动窗口、单调栈怎么用？

想用滑动窗口，要想办法把具体的问题转化为滑动窗口的处理流程
想用滑动窗口最值的更新结构，就看看处理流程下，是否需要最值这个信息
想用单调栈，要想办法把具体的问题转化为单调栈所解决的原问题
滑动窗口及其最大值和最小值的更新结构、单调栈，都是重要算法原型

  • 给定一个只包含正数的数组arr，arr中任何一个子数组sub，
    一定都可以算出(sub累加和 )* (sub中的最小值)是什么，
    那么所有子数组中，这个值最大是多少？
public class MaxSum {
    public static int maxSum(int[] arr){
        int[] sum = new int[arr.length];
        sum[0] = arr[0];
        for (int i = 1;i < arr.length ;i++){
            sum[i] = sum[i -1] + arr[i];
        }
        int[][] ints = monotonousStack2(arr);
        int max = Integer.MIN_VALUE;
        for (int i = 0;i < ints.length;i++){
            // 以当前元素为最小值的子数组
            int left = ints[i][0];
            int right = ints[i][1];
            // left 和 right 之间的和
            int he = 0;
            if(left == -1){
                if(right == -1){
                    he = sum[sum.length-1];
                }else{
                    he = sum[right - 1];
                }
            }else {
                if(right == -1){
                    he = sum[sum.length-1] - sum[left];
                }else {
                    he = sum[right -1 ] - sum[left];
                }
            }
            max = Math.max(max,he*arr[i]);
        }

        return max;
    }

    // 数组中有重复元素
    public static int[][] monotonousStack2(int[] arr){
        if (arr == null || arr.length == 0) {
            return null;
        }

        int len = arr.length;
        Stack<List<Integer>> stack = new Stack<>();
        int[][] res = new int[len][2];
        int index = 0;
        int max = Integer.MIN_VALUE;
        while (index < len){
            while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[index]){
                List<Integer> pop = stack.pop();
                for(Integer item : pop){
                    int temp = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size()-1);
                    // 左边最近最小元素
                    res[item][0] = temp;
                    // 右边最近最小元素
                    res[item][1] = index;
                }

            }
            if(!stack.isEmpty() && arr[stack.peek().get(0)] == arr[index]){
                stack.peek().add(index);
            }else {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(index);
                stack.push(list);
            }
            index ++;
        }

        while (!stack.isEmpty()) {
            List<Integer> list = stack.pop();
            for(Integer item : list){
                int temp = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size()-1);
                res[item][0] = temp;
                res[item][1] = -1;
            }
        }

        return res;

    }

    public static int max2(int[] arr) {
        int size = arr.length;
        int[] sums = new int[size];
        sums[0] = arr[0];
        for (int i = 1; i < size; i++) {
            sums[i] = sums[i - 1] + arr[i];
        }
        int max = Integer.MIN_VALUE;
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i < size; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                int j = stack.pop();
                max = Math.max(max, (stack.isEmpty() ? sums[i - 1] : (sums[i - 1] - sums[stack.peek()])) * arr[j]);
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            int j = stack.pop();
            max = Math.max(max, (stack.isEmpty() ? sums[size - 1] : (sums[size - 1] - sums[stack.peek()])) * arr[j]);
        }
        return max;
    }
    
}
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 203,456评论 5赞 477
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,370评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,337评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,583评论 1赞 273
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,596评论 5赞 365
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,572评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,936评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,595评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,850评论 1赞 297
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,601评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,685评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,371评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,951评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,934评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,167评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 43,636评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,411评论 2赞 342