题目：给定一个二维数组matrix,数组中的每个元素代表一棵树的高度。你可以选定连续的若干行组成防风带，防风带每一列的防风高度为这一列的最大值防风带整体的防风高度为，所有列防风高度的最小值。比如，假设选定如下三行1 5 47 2 62 3 41、7、2的列，防风高度为75、2、3的列，防风高度为54、6、6的列，防风高度为6防风带整体的防风高度为5，是7、5、6中的最小值给定一个正数k, k <= matrix的行数，表示可以取连续的k行，这k行。一起防风。求防风带整体的防风高度最大值思路：这道题其实很直白，按照题意要求一步一步求就可以。每次选定连续的k行，其实就是一个窗口,防风带整体的防风高度就是选定的k行每列最大值中的最小值。遍历整个二维数组，所有的k行防风带中的最大值即是答案。代码：int maxHeightWindProof(vector<vector<int>> & matrix, int k) { if (matrix.size() == 0) { return 0; } int m = (int
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。leetcode原题：https://leetcode.cn/problems/sliding-window-maximum思路:直观思路就是暴力，暴力是万能的。每向右滑动一下，都有k个数，遍历这k个数，可以得到一个最大值。维持k个数的最大值，还有一个方法也很直观，就是使用优先队列，即大根堆。时空复杂度更好的就是使用双端队列，让队列里的数，时刻保持单调递减。这样每次取最大值的时候直接使用队列头部的数即可。使用双端队列的时候，入队的是什么也很重要，一开始想的是入数组里的数，发现窗口左端右移的时候不好判断。而把下标入队，就非常容易了。代码：vector<int> maxSlidingWindow(vector<int>& nums, int k) { vector<int> ans; deque<int> window; for
给定一个整数组成的无序数组arr,值可能正、可能负、可能0 哪个子数组含有0和1的数量一样，并且是长度最大的，返回其长度思路:这道题和子数组和等于target的题很像，那能不能转换为那道题?本题数组内的元素只有三种，既不是0也不是1，0，1。既不是0也不是1转变为0，0转变为-1。那么含有相同数量0、1的子数组和就为0。就和子数组和等于target的题一样了。代码：int subArrayMaxLength2(vector<int> &arr) { vector<int> newArr; for(int i = 0;i < arr.size();i++) { if (arr[i] != 0 && arr[i] != 1) { newArr.push_back(0); } else if (arr[i] == 0) { newArr.push_back(-1); } else if (arr[
给定一个有序数组arr,代表坐落在X轴上的点给定一个正数K,代表绳子的长度返回绳子最多压中几个点?即使绳子边缘处盖住点也算盖住思路:一根绳子是一个窗口，用绳子的左端盖住第i个点arr[i],看右端能盖住第几个点，得到一个答案，从左到右依次遍历arr,得到所有点的答案，再求最大值即可。代码:int maxQuantity(vector<int> & arr, int k) { int ans = 0,right = 0; for(int i = 0;i < arr.size();i++) { while (right < arr.size() && arr[right] - arr[i] <= k) { right++; } ans = max(ans, right - i); } return ans; }
给定一个数组arr,其中可能有正、有负、有0，给定一个整数target,返回arr中所有子数组里，累加和等于target的子数组长度最大是多少?思路:最简单直观的思路就是暴力，两个for循环，枚举所有子数组，看和是否等于target,如果等于就记下长度，找出最长就可以了。这样的时间复杂度是O(n^2)。使用前缀和的方法可以使时间复杂度到O(n)。做法是遍历数组，走到下标 i ，计算从0到 i 的和sum，并且记住这个和sum和i，同时看记忆中是否有 sum-target 的记录，如果有记录并且记录的下标为i'，则代表找到一个子数组[i',i]满足和等于target。代码:int maxLength(vector<int> &arr, int target) { if (arr.size() == 0) { return 0; } unordered_map<int, int> map; map.insert({0,-1}); int sum = 0; int ans = 0; for
