862. 和至少为 K 的最短子数组

862. 和至少为 K 的最短子数组

---

C代码：前缀和 + 单调双端队列
这才是真谛啊，这道题根本就不涉及到循环队列，没有必要使用循环队列！
也没有必要使用设计题的形式，太过于使用形式，导致思考的重点不在算法上了，设计题用在规范的工程当中！

int shortestSubarray(int* nums, int numsSize, int k){
    int queueIndex[numsSize + 1];
    int front = 0;
    int rear = 0;

    long long presum[numsSize + 1]; // 注意long long
    presum[0] = 0;
    for(int i = 0 ; i < numsSize; ++ i){  
        presum[i + 1] = presum[i] + nums[i];
    } 

    int minCount = INT_MAX;
    for(int i = 0; i <= numsSize; ++i ){
        while(front < rear && presum[i] < presum[queueIndex[rear - 1]]){  // 维持单调递增队列！
            rear--;
        }
        queueIndex[rear++] = i; 
        while(front < rear && (presum[i] - presum[queueIndex[front]]) >= k){
            minCount = fmin(minCount, i - queueIndex[front]);
            front++;
        } 
    }
    return minCount == INT_MAX ? -1 : minCount;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

C代码：前缀和 + 单调双端队列

// 1、子数组的和>=k  2、最短非空子 的长度

typedef struct {
    int *elements;  // 指针，指向数组
    int rear;       // 数组尾
    int front;      // 数组头
    int capacity;   // 数组大小
} MyCircularDeque;

// 使用的是设计题的做法！
MyCircularDeque* myCircularDequeCreate(int k) {
    MyCircularDeque *obj = (MyCircularDeque *)malloc(sizeof(MyCircularDeque));  // 创建一个结构体指针
    obj->capacity = k + 1;
    obj->rear = 0;
    obj->front = 0;
    obj->elements = (int *)malloc(sizeof(int) * obj->capacity);  // 创建数组
    return obj;
}

bool myCircularDequeInsertFront(MyCircularDeque* obj, int value) {
    if ((obj->rear + 1) % obj->capacity == obj->front) {  // rear 与 front 并列即为满！
        return false;                                     // 构造的时候多构造了一个位置，rear指向空位置；1 2 3 _ 4 5(rear指向_、front指向4，此时就满了)
    }
    obj->front = (obj->front - 1) % obj->capacity;
    obj->elements[obj->front] = value;
    return true;
}

bool myCircularDequeInsertLast(MyCircularDeque* obj, int value) {  // 用一个结构体指针
    if ((obj->rear + 1) % obj->capacity == obj->front) { // 没有位置插入了，插入rear与front就重合了
        return false;
    }
    obj->elements[obj->rear] = value;
    obj->rear = (obj->rear + 1) % obj->capacity;   // 循环队列
    return true;
}

bool myCircularDequeDeleteFront(MyCircularDeque* obj) {
    if (obj->rear == obj->front) {
        return false;
    }
    obj->front = (obj->front + 1) % obj->capacity;
    return true;
}

bool myCircularDequeDeleteLast(MyCircularDeque* obj) {
    if (obj->rear == obj->front) {  // 两指针相遇即结束
        return false;
    }
    obj->rear = (obj->rear - 1) % obj->capacity;
    return true;
}

int myCircularDequeGetFront(MyCircularDeque* obj) {
    if (obj->rear == obj->front) {
        return -1;
    }
    return obj->elements[obj->front];
}

int myCircularDequeGetRear(MyCircularDeque* obj) {
    if (obj->rear == obj->front) {
        return -1;
    }
    return obj->elements[(obj->rear - 1) % obj->capacity];  // obj->rear 一直使用的是求余
}

bool myCircularDequeIsEmpty(MyCircularDeque* obj) {
    return obj->front == obj->rear;
}

bool myCircularDequeIsFull(MyCircularDeque* obj) {
    return (obj->rear + 1) % obj->capacity == obj->front;
}

void myCircularDequeFree(MyCircularDeque* obj) {
    free(obj->elements);  // 释放数组内存
    free(obj);  // 释放结构体内存
}

#define MIN(a, b) ((a) < (b) ? (a) : (b))

int shortestSubarray(int* nums, int numsSize, int k) {
    long preSumArr[numsSize + 1];
    preSumArr[0] = 0;

    for (int i = 0; i < numsSize; i++) {   // 构造前缀和
        preSumArr[i + 1] = preSumArr[i] + nums[i];
    }

    int res = INT_MAX;  
    MyCircularDeque *queue = myCircularDequeCreate(numsSize + 1);  // 

    for (int i = 0; i <= numsSize; i++) {
        long curSum = preSumArr[i];                              // 队列从头到尾：前缀和依次变大（全是正数）
        while (!myCircularDequeIsEmpty(queue) && curSum - preSumArr[myCircularDequeGetFront(queue)] >= k) {
            res = MIN(res, i - myCircularDequeGetFront(queue));  // [84,37,32,40,95] 
            myCircularDequeDeleteFront(queue);
        }                                        // 即遇到负数，使和减小，那么队列中就不保存之前的前缀和；维持前缀和-单调递增队列！
        while (!myCircularDequeIsEmpty(queue) && preSumArr[myCircularDequeGetRear(queue)] >= curSum) {  
            myCircularDequeDeleteLast(queue);                       // [84,-37,32,40,95] 
        }                                                           // curSum = 84 -37 
                                                                    // que: 84
        myCircularDequeInsertLast(queue, i);  // 将下标index插入双端队列
    }

    myCircularDequeFree(queue);

    return res == INT_MAX ? -1 : res;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111