Thuật toán Left Right tìm Min/Max

1. Phát biểu bài toán tìm min/max

Cho mảng A có n phần tử \(A_1, A_2, …, A_n \)

Yêu cầu: Tìm các cặp số \(L_i, R_i\) thỏa mãn:

• \(A_i \)là \(min\) của đoạn \(L_i\) đến \(R_i\)
• \(R_i − L_i + 1\) là lớn nhất

2. Ý tưởng

Thuật toán ngây thơ
Độ phức tạp \(O(n^2)\)

for (int i = 1; i <= n; ++i ) {
	l[i] = i;
	int j = i;
	while(j > 1 && a[j-1] >= a[i]) j--;
}
for (int i = n; i > 0; --i) { 
	r[i] = i;
	int j = i;
	while(j < n && a[j+1] >= a[i]) j++;
}

Thuật toán Left Right
Thay vì từ một vị trí \(i\), ta sử dụng một vòng while lặp từ vị trí đó sang trái/phải để tìm phần tử đầu tiên lớn hơn hoặc bằng \(a[i]\). Thuật toán Left Right sử dụng kết quả \(L[i], R[i]\) từ những vị trí đã tính được trước đó để cập nhật cho vị trí hiện tại.

Nhận xét

• Xét vị trí \(i\), ta có \(A[i]\) là min trong đoạn từ \(L[i]\) đến \(i\).
• Xét vị trí \(L[i]-1\), ta có \(A[L[i]-1]\) là min trong đoạn từ \(L[L[i]-1]\) đến \(L[i]-1\)
• Vậy nếu \(A[L[i]-1] >= A[i]\) thì có nghĩa là \(A[i]\) sẽ là min trong đoạn \(L[L[i]-1] \) đến \(i\)

Vậy để tìm \(L[i]\) ta tiến hành nhảy cóc để nới đoạn \(L[i]\) đến khi không nhảy được nữa.

3. Cài đặt Thuật toán Left Right

for (int i=1; i<=n;++i ) {
	l[i] = i; // min = a[i]
	int k = i-1;
	while (k>0 && a[i] <= a[k]) {
		l[i] = l[k];
		k = l[k] - 1; // nhảy cóc 
	}
}
for (int i=n; i>0;--i) { 
	r[i] = i;
	int k = i+1;
	while (k<n && a[i] <= a[k]) {
		r[i] = r[k];
		k = r[k] + 1; 
	}
}

4. Đánh giá độ phức tạp của Thuật toán Left Right

Độ phức tạp của thuật toán là \(O(N * alpha)\) trong đó \(alpha\) là số lần nhảy cóc. Trên thực tế, số lần nhảy cóc rất nhỏ, do đoạn sau sẽ sử dụng kết quả nhảy cóc của đoạn trước nên ta có thể coi \(alpha\) là \(O(1)\).
Vậy độ phức tạp của thuật toán \(O(N)\)

5. Luyện tập

Đây là một số bài tập luyện tập trong sách Competitive Programming Basic của Code Dream, đăng ký mua ngay để được luyện tập nhiều dạng bài về thuật toán khác, chấm bài online tại http://oj.codedream.edu.vn 

Xem thêm tại: https://codedream.edu.vn/hoc-thuat-toan/ và https://www.facebook.com/codedreamedu

Áp dụng giải bài PALLETS

Ý tưởng là thay vì thử từng độ dài cạnh của hình vuông, ta sẽ xét lần lượt từng tấm ván và coi chiều cao của tấm ván chính là cạnh hình vuông cần tìm.
Bài toán trở thành: Kiểm tra xem với chiều cao \(A[i]\), có tìm được ít nhất \(A[i]\) tấm ván liền nhau (phải chứa tấm ván \(i\)) hay không?
Dễ thấy, một tấm ván lân cận tấm ván \(i\) mà ghép vào để tạo hình vuông có chiều cao \(A[i]\) thì tấm ván đó phải có chiều cao \(>=A[i]\).
Vậy, với mỗi vị trí \(i\), ta đi tìm \(L[i], R[i]\) là hai vị trí bên trái và bên phải xa \(i\) nhất mà đoạn từ \(L[i]\) và \(R[i]\) nhận \(A[i]\) làm \(min\), khi đó \(R[i]-L[i]+1\) sẽ là chiều rộng tối đa mà ta có thể ghép được. Nếu chiều rộng này \(>=A[i]\) thì tức là có thể ghép được thành hình vuông có chiều cao là \(A[i]\).

Code mẫu PALLETS C++

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
int a[maxn], l[maxn], r[maxn];
int main() {
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	//Tính mảng L
	for (int i = 1; i <= n; ++i ) {
		l[i] = i; // min = a[i]
		int k = i - 1;
		while (k > 0 && a[i] <= a[k]) {
			l[i] = l[k];
			k = l[k] - 1; // nhảy cóc 
		}
	}
	//Tính mảng R
	for (int i = n; i > 0; --i) { 
		r[i] = i;
		int k = i + 1;
		while (k < n && a[i] <= a[k]) {
			r[i] = r[k];
			k = r[k] + 1; 
		}
	}
	int res = 0;
	//Tính kết quả
	for (int i=1; i<=n;++i ) {
		if ( a[i] <= r[i] - l[i] + 1){
			res = max(res, a[i]);
		}
	}
	cout << res;
	return 0;
}