casyup.me@outlook.com

0%

leetcode/PartitionArrayintoDisjointintervals

Posted on

Partition Array into Disjoint intervals

我的思维好像固定了 = =…

my solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int partitionDisjoint(vector<int>& A) {
        int b = 0, e = A.size() - 1;
        int lx = A[b];
        while (b < e) {
            while (e > b && A[e] >= lx) { --e; }
            // A[e] will less than lx
            
            int olx = lx;
            while (b < e) {
                lx = max(lx, A[++b]);
            }
            // lx is max[A[0] - A[e]]
            
            if (olx != lx) {
                // recalculate
                e = A.size() - 1;
            }
        }
        
        return b + 1;
    }
};

lx 是左边已遍历最大值. e 在每次遍历后将会指向一个从右往左第一个小于这个值的下标.

b 的迭代不会重复, 而 e 的迭代是可能重复的, 这是这个解法的瓶颈.

other solution

PS: 以后没有 the best solution 了. 因为很难说一个算法是 best 的. 因为实际的输入不定. 适用于输入的算法也不定. 并且提交里面往往并不是最好的算法. Discuss 里面才有.

参照

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int partitionDisjoint(vector<int>& A) {
        int b = 0, e = 0;
        int lx = A[b], rlx = lx;
        for (int i = 0; i < A.size(); ++i) {
            if (A[i] < lx) {
                e = i;
                lx = rlx;
            } else if (A[i] > rlx) {
                rlx = A[i];
            }
        }
        
        //printf("rlx: %d, lx: %d", rlx, lx);
        return e + 1;
    }
};

毫无疑问是比我更好的解法.

唯一可能的疑问是每次迭代所使用的条件有些许复杂. 极端条件如: A {1, 2, 3 … } 下. 这个算法会赋值多次.

而我的解法相对会少很多. (这也是我说大多数情况下不存在 best 的原因)

让我反思的是, 我的思维可能出现了僵化. 一开始我想的办法就是首尾逼近的方式. 所以最后的解法也是类似的结构.

这不禁让我想起之前好像在某个视频中看到的片段. 大意是说: 一个侦探在侦破案件时会让自己忘记一些常识性的东西. 因为这常常会误导自己而忽视重要线索. 或许解法也是如此. 经验同时也可能成为阻止你创新的障碍.

所以有时会有”砍掉重学”这种概念. 我应该想办法规避这种情况. 毕竟”不要让你已获得的东西成为你获取其他东西的障碍”是我坚持的理念.