ปูพื้นฐาน

สองตัวชี้กับหน้าต่างเลื่อน: เลิกนับใหม่ทุกช่วง แล้วเหลือแค่สองรอบของอาเรย์

คำถามเรื่องช่วงติดกันเกือบทุกแบบยุบจากกำลังสองเหลือเชิงเส้นได้ ถ้าตอบคำถามเดียวถูก คือขอบซ้ายมีทางถอยกลับไหม บทนี้ให้กฎตัดสินข้อนั้น พร้อมรูปมาตรฐานสองแบบและโจทย์ฝึกที่คนเขียนพลาดบ่อยที่สุด

ปัญหาที่บทนี้แก้

โจทย์จำนวนมากถามถึงช่วงติดกันของอาเรย์หรือสตริง เช่น ช่วงที่ยาวที่สุดที่ผลรวมไม่เกินเท่านี้ ช่วงที่สั้นที่สุดที่มีของครบทุกชนิด หรือช่วงยาวคงที่ที่มีของตรงตามที่กำหนด

ท่าแรกที่ทุกคนคิดออกคือไล่ทุกคู่ของขอบซ้ายขอบขวา ซึ่งเป็น n² ช่วง แค่ n เป็นหมื่นก็เริ่มไม่ไหว ส่วนบทนี้จะให้ท่าที่เดินขอบซ้ายกับขอบขวาไปข้างหน้าอย่างเดียว คนละรอบ ซึ่งได้คำตอบเดียวกันในเวลาเชิงเส้น

กติกาข้อเดียวที่ทำให้ท่านี้ใช้ได้

หน้าต่างเลื่อนใช้ได้เมื่อการขยายขอบขวาทำให้เงื่อนไขแย่ลงเสมอ และการหดขอบซ้ายทำให้ดีขึ้นเสมอ เรียกคุณสมบัตินี้ว่าความเอกโทน (monotone)

ตัวอย่างที่ใช้ได้ ผลรวมของจำนวนเต็มบวก ยิ่งขยายยิ่งมาก จำนวนชนิดที่ต่างกันในช่วง ยิ่งขยายยิ่งไม่ลด ส่วนตัวอย่างที่ใช้ไม่ได้คือผลรวมของอาเรย์ที่มีเลขติดลบปนอยู่ เพราะขยายแล้วผลรวมอาจน้อยลง ขอบซ้ายที่เคยต้องเลื่อนอาจต้องถอยกลับ ซึ่งทำลายเหตุผลทั้งหมด

รูปมาตรฐาน

โครงของหน้าต่างเลื่อนมีแค่สองแบบ และแทบทุกโจทย์เข้าแบบใดแบบหนึ่ง

• ยาวที่สุดที่ยัง "ผ่าน" ขยายขวาไปเรื่อย ๆ เมื่อไรที่หลุดเงื่อนไข ก็หดซ้ายจนกลับมาผ่าน แล้วบันทึกความยาว
• สั้นที่สุดที่ "ผ่าน" แล้ว ขยายขวาไปเรื่อย ๆ เมื่อไรที่ผ่านเงื่อนไข ก็หดซ้ายเท่าที่ยังผ่านอยู่ แล้วบันทึกความยาวระหว่างหด

ทั้งสองแบบมีจุดร่วมเดียวกันคือ l กับ r ไม่เคยถอยหลัง แต่ละตัวจึงเดินได้มากที่สุด n ก้าว รวมเป็น 2n ก้าวตลอดโปรแกรม ไม่ว่าลูปข้างในจะดูน่ากลัวแค่ไหน

ลองเอง · ลากหน้าต่างหาช่วงที่ยาวที่สุด

ถ้าเล่นจนจบได้โดยตัวนับถอยยังเป็นศูนย์ แปลว่าคุณเพิ่งค้นพบเงื่อนไขที่ทำให้ท่านี้เร็วด้วยตัวเอง

โจทย์ฝึกข้อที่ 1 · ช่วงที่ยาวที่สุดที่ผลรวมไม่เกิน S

ให้อาเรย์ของจำนวนเต็มบวกยาว n กับเลข S หาความยาวของช่วงติดกันที่ยาวที่สุดซึ่งผลรวมไม่เกิน S

เฉลยข้อที่ 1

// ช่วงติดกันที่ยาวที่สุดซึ่งผลรวมไม่เกิน S  (ทุกตัวเป็นจำนวนเต็มบวก)
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; long long S;
    scanf("%d %lld", &n, &S);
    vector<long long> a(n);
    for (auto& v : a) scanf("%lld", &v);
    long long sum = 0; int best = 0, l = 0;
    for (int r = 0; r < n; r++) {
        sum += a[r];
        while (sum > S) sum -= a[l++];       // ขอบซ้ายเดินหน้าอย่างเดียว ไม่มีวันถอย
        best = max(best, r - l + 1);
    }
    printf("%d\n", best);
}

โจทย์ฝึกข้อที่ 2 · ช่วงที่สั้นที่สุดที่มีครบทุกชนิด

ให้อาเรย์ยาว n ที่สมาชิกเป็นเลข 1 ถึง K หาความยาวของช่วงติดกันที่สั้นที่สุด ซึ่งมีเลขครบทั้ง K ชนิด ถ้าไม่มีให้ตอบ -1

เฉลยข้อที่ 2

// ช่วงติดกันที่สั้นที่สุดซึ่งมีค่าครบทั้ง K ชนิด  (ค่าในอาเรย์อยู่ระหว่าง 1 ถึง K)
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, K;
    scanf("%d %d", &n, &K);
    vector<int> a(n);
    for (auto& v : a) scanf("%d", &v);
    vector<int> cnt(K + 1, 0);
    int have = 0, best = INT_MAX, l = 0;
    for (int r = 0; r < n; r++) {
        if (cnt[a[r]]++ == 0) have++;        // ชนิดนี้เพิ่งโผล่ครั้งแรกในหน้าต่าง
        while (have == K) {                  // ครบแล้ว หดขอบซ้ายให้สั้นที่สุดเท่าที่ยังครบ
            best = min(best, r - l + 1);
            if (--cnt[a[l++]] == 0) have--;
        }
    }
    printf("%d\n", best == INT_MAX ? -1 : best);
}

อีกท่าหนึ่งที่ต้องมี · เมื่อคำถามเปลี่ยนจากผลรวมเป็นค่ามากสุด

ท่าหน้าต่างเลื่อนที่ผ่านมาทั้งบทยืนอยู่บนกติกาข้อเดียว คือตอนตัวเข้าตัวออก เราต้องอัปเดตคำตอบของหน้าต่างได้ทันที ผลรวมทำได้ เพราะบวกตัวที่เข้าและลบตัวที่ออกก็จบ แต่ถ้าโจทย์เปลี่ยนคำถามเป็น ค่ามากที่สุดของทุกหน้าต่างกว้าง k กติกานั้นพังทันที

ที่พังเพราะการลบ ตอนตัวซ้ายหลุดออกจากหน้าต่าง ถ้าตัวที่หลุดนั้นดันเป็นตัวที่มากที่สุดอยู่ เราจะไม่มีข้อมูลอะไรเหลือให้กู้คำตอบใหม่เลย รู้แค่ว่าค่ามากสุดเดิมเท่าไร ซึ่งใช้ไม่ได้แล้ว ทางที่เห็นชัดที่สุดคือกวาดหาใหม่ทั้งหน้าต่าง แต่นั่นคือ k ครั้งต่อหนึ่งก้าว ซึ่งพาเรากลับไปที่ปัญหาเดิมที่บทนี้เปิดเรื่องด้วย

ข้อสังเกตที่ทิ้งของได้ทั้งกอง

ลองถามคำถามที่แคบกว่าเดิม แทนที่จะถามว่า "ค่ามากสุดคืออะไร" ให้ถามว่า ตำแหน่งไหนยังมีสิทธิ์เป็นคำตอบในอนาคตอยู่บ้าง

สมมติมีสองตำแหน่ง j กับ r โดย j อยู่ก่อน r และ a[j] ≤ a[r] ตำแหน่ง j จะไม่มีวันได้เป็นคำตอบอีกเลย เพราะทุกหน้าต่างที่ยังมี j อยู่ ก็มี r อยู่ด้วยแน่ ๆ (r อยู่ทางขวาและหน้าต่างเลื่อนไปทางขวาเท่านั้น) และ r ก็ไม่เล็กกว่า เก่ากว่าและไม่ใหญ่กว่า จึงไร้ประโยชน์ถาวร ทิ้งได้เลย

พอทิ้งของแบบนั้นได้ ตำแหน่งที่เหลืออยู่ในมือจะมีค่าเรียงจากมากไปน้อยโดยอัตโนมัติ เพราะทุกคู่ที่ผิดลำดับถูกทิ้งไปแล้ว และเมื่อมันเรียงอยู่แล้ว ค่ามากสุดของหน้าต่างก็คือตัวหัวแถว ไม่ต้องหาอะไรอีก

โครงสร้างที่รับของเข้าท้ายแถว ทิ้งของจากท้ายแถว และทิ้งของที่หมดอายุจากหัวแถวได้ด้วย เรียกว่าแถวสองหัว (deque ย่อจาก double-ended queue อ่านว่า "เด็ก") และเมื่อเราคุมให้ค่าในนั้น เรียงทางเดียวตลอด ก็เรียกรวมกันว่าแถวสองหัวที่เรียงทางเดียว (monotonic deque)

ทำไมมันไม่แพง ทั้งที่มีลูปซ้อนอยู่

ในโค้ดข้างล่างมี while ซ้อนอยู่ใน for ซึ่งหน้าตาเหมือน O(n²) แต่มันไม่ใช่ เพราะทุกตำแหน่งเข้าแถวได้ครั้งเดียวและออกจากแถวได้ครั้งเดียว งานทั้งการเดินจึงมีเพดานที่ 2n ครั้ง ไม่ว่าลูปในจะวนยาวแค่ไหนในบางก้าว วิธีนับต้นทุนแบบมองยอดรวมแทนการมองก้าวที่แย่ที่สุด เรียกว่าการนับแบบเฉลี่ยทบ (amortized) ซึ่งเป็นวิธีนับเดียวกับที่ทำให้ท่าสองตัวชี้ในบทนี้ถูกตั้งแต่ต้น

// ค่ามากที่สุดของทุกหน้าต่างกว้าง k ด้วยแถวสองหัวที่เรียงลด
// dq เก็บ "ตำแหน่ง" ไม่ใช่ค่า และค่าที่ตำแหน่งเหล่านั้นเรียงจากมากไปน้อยเสมอ
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k; scanf("%d %d", &n, &k);
    vector<int> a(n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    deque<int> dq;
    for (int r = 0; r < n; r++) {
        // ตัวใหม่ใหญ่กว่าหรือเท่าตัวท้ายแถว ตัวท้ายจึงหมดสิทธิ์เป็นคำตอบตลอดกาล
        // เพราะมันทั้งเก่ากว่าและไม่ใหญ่กว่า ทิ้งได้เลยโดยไม่ต้องกลัวเสียคำตอบ
        while (!dq.empty() && a[dq.back()] <= a[r]) dq.pop_back();
        dq.push_back(r);
        // หัวแถวหลุดออกนอกหน้าต่างไปแล้ว
        if (dq.front() <= r - k) dq.pop_front();
        // หน้าต่างเต็มแล้ว หัวแถวคือค่ามากสุดของหน้าต่างนี้
        if (r >= k - 1) printf("%d%c", a[dq.front()], r + 1 == n ? '\n' : ' ');
    }
    return 0;
}

// ตัวตรวจอิสระ กวาดทุกหน้าต่างแล้วหาค่ามากสุดตรง ๆ
// มันไม่รู้จักข้ออ้างเรื่อง "เก่ากว่าและเล็กกว่า" เลย จึงไม่ได้ทดสอบแค่การพิมพ์
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k; scanf("%d %d", &n, &k);
    vector<int> a(n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int l = 0; l + k <= n; l++) {
        int best = a[l];
        for (int j = l; j < l + k; j++) best = max(best, a[j]);
        printf("%d%c", best, l + k == n ? '\n' : ' ');
    }
    return 0;
}

ท่านี้ยกไปใช้ได้กว้างกว่าที่คิด รูปทั่วไปของมันคือ ถ้าของชิ้นหนึ่งทั้งเก่ากว่าและแย่กว่าอีกชิ้น มันไร้ประโยชน์ถาวร พอเจอโจทย์ที่ต้องรู้ค่าที่ดีที่สุดของช่วงที่เลื่อนไปทางเดียว ให้ลองถามประโยคนี้ก่อน ถ้าตอบว่าใช่ ก็เก็บของที่ยังมีสิทธิ์ไว้ในแถวเดียว แล้วคำตอบจะรออยู่ที่หัวแถวเสมอ ญาติสนิทของมันคือสแต็กที่เรียงทางเดียว (monotonic stack) ซึ่งตอบคำถามว่า "ตัวถัดไปที่ใหญ่กว่าอยู่ที่ไหน" ด้วยข้ออ้างเดียวกันเป๊ะ

เอาไปใช้ที่ไหนในคลังนี้

• นับคำที่เขียนสลับที่ได้ ใช้หน้าต่างยาวคงที่ พร้อมตัวนับชนิดที่พอดี
• เส้นทางที่ยาวที่สุดบนเกาะ ใช้หน้าต่างเลื่อนบนวงที่คลี่เป็นสองรอบ พร้อมคิวสองหัวเพื่อเก็บค่ามากสุดในหน้าต่าง ซึ่งเป็นญาติสนิทของบทนี้

สรุปบรรทัดเดียว

ถ้าขยายขอบขวาแล้วขอบซ้ายไม่มีทางถอยกลับ ก็ไม่ต้องเริ่มนับใหม่ทุกรอบ ปล่อยให้ตัวชี้ทั้งสองเดินหน้าอย่างเดียว แล้วต้นทุนทั้งโปรแกรมจะเป็นสองรอบของอาเรย์ ไม่ว่าลูปซ้อนกันจะดูน่ากลัวแค่ไหน