本文共 5715 字，大约阅读时间需要 19 分钟。

 解题思路：

一、先试试暴力求解。

对于不同的起点

1.如果起点是负数，终止

2.起点依次向后累加，如果累加的值小于等于0，终止

3.如果累加的值大于等于K，符合条件，记录长度。最后选取最短的长度

复杂度为，超时。

代码如下：

int shortestSubarray(vector
   
    & A, int K) {        int length = INT_MAX;        int size = A.size();        int i, j;        for(i = 0; i < size; i++) {            if(A[i] < 0)                continue;            int sum = 0;            for(j = i; j < size; j++) {                sum += A[j];                if(sum >= K || sum <= 0 || j-i+1 >= length)                    break;            }            if(sum >= K) {                int c = j-i+1;                length = length>c?c:length;            }        }        if(length == INT_MAX)            length = -1;        return length;    }
   

二、换个思路，尝试使用队列

先对数组A进行一个预处理，使用一个数组p，p[n] = 0 + A[0] + A[1] + ... + A[n-1]  (n >= 0)

那么p[i] - p[j] 也就是原数组中的某一段连续的值了(i > j)。

规则1：如果p[i] - p[j] <= 0 ，也就是这一段值的累加为非正数，和暴力求解里同样处理——终止。

规则2：如果p[i] - p[j] >= K, 也就是说这一段值的累加满足条件，停止对p[j]的继续处理(如果还以j为起点的话，只能得到更长的长度)记录长度(p[i] - p[j], 不需要再+1), 之后从中选取最短的。

所以实际上用的思想和暴力求解没有什么区别。

算法过程：

维护一个双头队列，将p中的值逐个放到队尾。每加入一个新值，需要进行如下处理：

1. 如果队尾比要加入的值大，删除队尾，直到队尾比要加入的值小

2. 如果这个值与队头的差大于等于K，记录长度，删除队头

在这个过程中，我们维护的队列是按升序排列的，所以——为了满足规则1，我们从后往前找，为了满足规则2，我们看队头。

代码如下：

int shortestSubarray(vector
   
    & A, int K) {        int length = INT_MAX;        vector
    
      p;        int sum = 0;        for(auto &i: A) {            p.push_back(sum);            sum += i;        }        p.push_back(sum);        int size = p.size();        deque
     
       dq;        for(int i = 0; i < size; i++) {            while(!dq.empty() && p[i] < p[dq.back()])                dq.pop_back();            while(!dq.empty() && p[i]-p[dq.front()] >= K) {                length = min(length, i-dq.front());                dq.pop_front();            }            dq.push_back(i);        }        return length == INT_MAX?-1:length;    }
     
    
   

复杂度为

这个算法的巧妙之处在于，引入p数组，在一次遍历的过程中完成了需要的累加过程，而不是暴力求解中那样每次重新累加。

解题思路：

要解此题也就是要找到需要的idle的个数，为了减少idle的使用，应该优先处理出现频率高的任务，并使用其他任务插入间隔之中，否则最后频率高的任务会使用到额外的idle作为间隔。

代码如下：

struct task {    char type;    int num;};bool operator<(task a, task b) {    return a.num < b.num;}class Solution {public:    int leastInterval(vector
   
    & tasks, int n) {        int count[26] = {0};        int origin = tasks.size();        for(auto& i:tasks) {            count[i-'A']++;        }        priority_queue
    
      q1;        priority_queue
     
       q2;        for(int i = 0; i < 26; i++) {            if(count[i]) {                q1.push({i+'A', count[i]});            }        }        int idle = 0;        while(!q1.empty()) {            int size = n;            while(!q1.empty() && size+1) {                task t = q1.top();                t.num--;                q1.pop();                q2.push(t);                size--;            }            while(!q2.empty()) {                if(q2.top().num != 0)                    q1.push(q2.top());                q2.pop();            }            if(size+1 > 0 && q1.size() > 0) {                idle += size+1;            }        }        return origin + idle;    }};
     
    
   

 解题思路：

首先，需要一些前置知识。

1. 最大连续子序列的和的问题

  给定一个数组，如何从中选取出最一个连续的子序列，且它的和最大？ 举个例子，[2, -3, 3, 5] 中的最大子序列为[3,5]，和为8。

  算法：Kadane 算法

  代码如下：

int maxSubarry(vector
   
    & v) {        int sum = 0, max = 0;        int size = v.size();        for(int i = 0; i < size; i++) {            if(sum < 0)                sum = v[i];            else                sum += v[i];            max = max>sum?max:sum;        }        return max;    }
   

如果这一题去掉k这一限制，则可以使用Kadane算法找到二维矩阵里的最大字矩阵和。

2. 和小于k的最大连续子序列的问题

对于这一问题，Kadane 算法不再适用，不能简单的在原来的基础上对k进行判断。例如，[2,2,-1], k = 0, Kadane算法求得的所有子序列和为 2,4,3 ， 没有满足的子序列。但实际上子序列-1满足条件。

算法：

与上文的解法类似，也需要用到求和数组，即s[n] = 0 + v[0] + v[1] + ... + v[n-1]  (n >= 0)。在算法中我们需要使用到set。set会对插入的各个项进行排序，lower_bound函数可以帮助我们选出大于等于指定数值的第一个数。两个特性结合起来就可以得到大于等于指定数值的最小的数。因为s[i]-s[j]也就是中间的连续序列的和，所以要有s[i]-s[j] <= k  (i > j), 转换一下, 就是。我们要找s[i]-s[j] 中最大的且小于k的值，当s[i]指定时，就需要找到s[j]中最小的，而lower_bound函数可以帮我们更快地找到。之后再从这些满足条件的值中筛选出最大值，就是答案了。

另外，需要注意set初始时插入了值0。如果不这么做，将会影响后面的计算。例如，[2,1], k=3。如果不插入0，最小的sum为2，得到结果就为1，但正确答案应该为3。再例如[2,1], k=2，如果不插入0，第一个sum值2将被跳过(一开始set为空)，最后得到的结果为1，但正确答案应该为2。

代码如下：

int maxSubarry(vector
   
    & v, int k) {        int sum = 0, max = INT_MIN;        set
    
      s;        s.insert(0);        for(auto& i:v) {            sum += i;            auto j = s.lower_bound(sum-k);            if(j != s.end())                max = std::max(max, sum-*j);            s.insert(sum);        }        return max;    }
    
   

前置知识讲完了，那么如何将一维的算法运用到二维矩阵当中呢？

如图，L棒从左往右移动，每当L棒移动一格，R棒逐格从L棒的位置移动到末尾。在这一过程中，L棒和R棒与矩阵的上下边界围成的区域的所有情况就构成了竖着截取出矩阵的所有情况。那么接下来再在这个基础上横切？不，接下来可以直接使用解决和小于k的最大连续子序列的算法。对于每个矩阵，因为选取了某一列的一行，其他所有列的这一行都会被选中，所以我们可以简单地横向将矩形压缩为数组，然后执行算法。最后从所有候选中选出最大的即可。

如果不想看文字表述，也可以听(过程很清晰) 。

代码如下, 然而并没有用队列，与标题不符

class Solution {public:    int maxSubarry(vector
   
    & v, int k) {        int sum = 0, max = INT_MIN;        set
    
      s;        s.insert(0);        for(auto& i:v) {            sum += i;            auto j = s.lower_bound(sum-k);            if(j != s.end())                max = std::max(max, sum-*j);            s.insert(sum);        }        return max;    }    int maxSumSubmatrix(vector
     
      
       >& matrix, int k) {        int width = matrix[0].size();        int height = matrix.size();        int L = 0, R = 0;        int max = INT_MIN;        for(L = 0; L < width; L++) {            vector
       
         column(height, 0);            for(R = L; R < width; R++) {                for(int i = 0; i < height; i++)                    column[i] += matrix[i][R];                int cur_max = maxSubarry(column, k);                max = std::max(max, cur_max);            }        }        return max==INT_MIN?-1:max;    }};