Dùng stack tìm min/max

CTDL Stack có thể được sử dụng để tìm số gần nhất lớn hơn/ nhỏ hơn số đang xét đến trong 1 mảng. Ta có bài toán sau:

Mục lục

1. Bài toán

Cho mảng \(A\) có \(n\) phần tử \(a_{1}, a_{2}, …, a_{n}\), \(n < 10^{6}\). Với mỗi \(i\) từ \(1\) đến \(n\) ta cần tìm \(j\) gần nhất sao cho \(a_j > a_i\). Nếu không tồn tại \(j\), in ra \(-1\).

Nhận xét

Ta sẽ xét bài toán đơn giản hơn với \(j < i\) vì với trường hợp \(j > i\) ta chỉ cần đảo ngược lại mảng và áp dụng thuật toán tương tự với trường hợp \(j < i\).

Thuật toán ngây thơ

Với mỗi \(i\) ta sẽ for \(j\) từ 1 đến \(n\) để tìm phần tử gần \(i\) nhất và lớn hơn \(a_{i}\). Thuật toán có độ phức tạp \(O(N^{2})\), không đủ để giải quyết bài toán trên.

Thuật toán cải tiến

Ta có mô hình sau:

Phần tử thứ \(i\) của mảng \(A\) tượng trưng cho một người có chiều cao \(a_{i}\).
Lần lượt người từ \(1\) đến \(n\) xếp thành một hàng. Người thứ \(i\) sẽ nhìn được người thứ \(j\) nếu \(j\) đứng trước \(i\) trong hàng.
Hàng luôn nhìn từ cuối về đầu.

Khi người thứ \(i\) xếp vào hàng, ta sẽ cải tiến việc xếp hàng như sau:

Thêm người đó vào cuối hàng.
Nếu người đứng trước thấp hơn người thứ \(i\), loại người đó ra khỏi hàng. Tiếp tục thao tác như vậy cho đến khi người đứng trước cao hơn người thứ \(i\).
Nếu người thứ \(i\) ở đầu hàng thì in ra \(-1\), ngược lại in ra chỉ số của người đứng trước \(i\).

Chứng minh

Giải thích: Người đứng đầu không có bất kì ai đứng trước họ nên sẽ có kết quả là \(-1\). Xét lần lượt các người tiếp theo, ta loại những người đứng trước \(i\) và thấp hơn \(i\) vì từ những người \(i+1\) sẽ không thể nhìn thấy những người bị loại này (do người thứ \(i\) cao hơn nên sẽ chắn hết những người bị loại này). Do đã loại hết những người thấp hơn đứng trước người thứ \(i\) nên sau khi loại hết, người đứng trước \(i\) chắc chắn là người cao hơn người thứ \(i\) và gần \(i\) nhất.
Chứng minh phản chứng: Lúc đầu, cho một người có chỉ số \(-1\), chiều cao \(+\infty\). Việc đứng đầu hàng có thể coi như đứng ngay sau người chỉ số \(-1\) này. Xét một người \(i\) bất kỳ ghi lại số \(j\), \(j < i\). Trước hết, \(a_j\) chắc chắn phải lớn hơn \(a_i\). Giả sử ngược lại, \(j\) không phải là người gần \(i\) nhất mà cao hơn người \(i\), mà \(k\) mới là người như vậy. Ta có \(j < k < i\) và \(a_k > a_i\). Tại thời điểm người \(i\) xếp vào hàng thì người \(k\) này không còn trong hàng nữa (nếu còn thì họ sẽ ghi lại người \(k\) chứ không phải \(j\)). Do đó, người \(k\) đã bị đuổi khỏi hàng bởi một người nào đó đứng sau \(k\) và trước \(i\). Gọi chỉ số của người đó là \(l\). Để đuổi người \(k\) thì \(a_l \geq a_k\). Từ đó ta có \(k < l < i, \ \ a_l \geq a_k > a_i\), trái với giả thiết \(k\) là người gần \(i\) nhất mà cao hơn \(i\). Như vậy, số mà mỗi người nhớ lại chính là chỉ số của người gần nhất cao hơn họ (\(-1\) nếu không tồn tại người như vậy). Đây chính là giá trị \(j\) cần tìm với mỗi \(i\).

Giả sử mảng \( A = { 1, 5, 2, 4, 3}\), thuật toán hoạt động như sau:

Cài đặt

Ta sẽ sử dụng 1 Stack để cài đặt bài toán trên:

Thao tác thêm người vào cuối hàng sử dụng hàm \(push\).
Thao tác loại người ra khỏi hàng sử dụng hàm \(pop\).

Code mẫu

stack<int> st;

for (int i = 1; i <= n; ++i)
{
    while (!st.empty() && a[st.top()] <= a[i])
        st.pop(); 
    int ans = -1;
    if (!st.empty())
        ans = st.top();
    cout << ans << ' ';
    st.push(i);
}

Độ phức tạp

Mỗi phần tử được \(push\) vào Stack 1 lần và bị \(pop\) tối đa 1 lần nên độ phức tạp của thuật toán là \(O(N)\).

2. Ứng dụng

Bài toán 1

Nguồn: SSAM219G SPOJ

Vẽ \(n\) cột hình chữ nhật sát nhau. Cột thứ \(i\) có chiều rộng \(1\) và chiều cao \(h_{i}\). Tìm hình chữ nhật có diện tích lớn nhất tạo bởi các cột.
Ví dụ: \(h = {2, 4, 4, 3, 2}\)
Hình chữ nhật lớn nhất có diện tích \(10\)

Nhận xét

Hình chữ nhật lớn nhất luôn có chiều cao bằng với chiều cao của một cột đã có.

Với mỗi cột \(i\), ký hiệu \(L_i\), \(R_i\) là cột gần nhất ở bên trái/phải \(i\) có chiều cao nhỏ hơn \(i\). Việc tìm cột gần nhất ở bên trái/phải cột \(i\) mà thấp hơn \(h_i\) chính là bài toán gốc nêu ở mục trước. Ta chỉ cần sửa đổi thay vì tìm cột cao hơn thì phải tìm cột thấp hơn.

Khi đã xác định các mảng \(L\) và \(R\), ta có thể xét từng cột \(i\) từ \(1\) đến \(n\). Giả sử hình chữ nhật có chiều cao bằng với cột đang xét. Khi đó, chiều dài lớn nhất của hình chữ nhật là từ cột gần nhất bên trái thấp hơn cột \(i\) đến cột gần nhất bên phải thấp hơn cột \(i\). Diện tích của hình chữ nhật lớn nhất qua cột \(i\) là: \((R_i – L_i – 1) * h_i\).

Vậy diện tích hình chữ nhật lớn nhất chính là giá trị \((R_i – L_i – 1) * h_i\) lớn nhất với mọi \(i\) từ \(1\) đến \(n\).

Độ phức tạp là \(O(n)\).

Code mẫu

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int int64_t
#define pii pair<int,int>
const int mx = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 1e18;
int n, a[mx], l[mx], r[mx], res;
void sub() {
	cin >> n;
	for (int i =1;i<=n;i++) cin >> a[i];
	stack<int> st;
	for (int i =1;i<=n;i++){
		while(!st.empty() && a[st.top()] >= a[i]) st.pop();
		if (st.empty()) l[i] = 1;
		else l[i] = st.top() + 1;
		st.push(i);
	}
	stack<int> st1;
	for (int i =n;i>=1;i--){
		while(!st1.empty() && a[st1.top()] >= a[i]) st1.pop();
		if (st1.empty()) r[i] = n;
		else r[i] = st1.top() - 1;
		st1.push(i);
	}
	for (int i =1;i<=n;i++){
		res = max(res,a[i] * (r[i] - l[i] - 1));
	}
	cout << res;
	
}
signed main() {
	#define name 
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if (fopen(name".inp", "r")) {
		freopen(name".inp", "r", stdin);
		freopen(name".out", "w", stdout);
	}
	sub();
	return 0;
}
//honguwu

Bài toán 2

Nguồn: qbrect VNOJ

Đây là một mở rộng của bài toán trước. Cho lưới ô vuông \(n \times m\), các ô có giá trị \(0\) hoặc \(1\). Ta cần tìm hình chữ nhật có diện tích lớn nhất có tất cả ô vuông có cùng giá trị.

Nhận xét

Ta có thể chia bài toán thành 2 trường hợp riêng biệt: tìm hình chữ nhật chỉ gồm các ô giá trị \(0\) và chỉ gồm các ô giá trị \(1\). Nếu giải được một trường hợp, ta cũng có thể dễ dàng giải trường hợp còn lại. Từ giờ, ta sẽ giải bài toán tìm hình chữ nhật lớn nhất chỉ chứa giá trị \(1\).

Ta xét lưới ô vuông con của lưới gốc, kích thước \(k \times m\). Nói cách khác, lưới ô vuông con này chính là \(k\) hàng đầu tiên của lưới gốc. Với mỗi \(k\) từ \(1\) đến \(n\), ta xét chiều cao của các cột chứa toàn số \(1\) dựng trên từng vị trí trong hàng. Sau đó, ta có thể áp dụng bài toán tìm hình chữ nhật lớn nhất tạo bởi các cột để giải quyết vấn đề.
Độ phức tạp là \(O(n \times m)\).

Code mẫu

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int int64_t
#define pii pair<int,int>
const int mx = 1e3 + 5;
const int mod = 1e9 + 7;
const int inf = 1e18;
int n,a[mx],h[mx], l[mx], r[mx], ans,m;
void sub() {
	cin >> n >> m;
	for (int i =1;i<=n;i++) {
		for (int j =1;j<=m;j++) {
			cin >> a[j];
			if (a[j]) h[j]++;
			else h[j] = 0;
		}
		stack<int> s1;
		for (int j =1;j<=m;j++){
			while(!s1.empty() && h[s1.top()] >= h[j]) s1.pop();
			if (s1.empty()) l[j] = 1;
			else l[j] = s1.top() + 1;
			s1.push(j);
		}
		stack<int> s2;
		for (int j =m;j>=1;j--){
			while(!s2.empty() && h[s2.top()] >= h[j]) s2.pop();
			if (s2.empty()) r[j] = m;
			else r[j] = s2.top() - 1;
			s2.push(j);
		}
		for (int j =1;j<=m;j++){
			ans = max(ans,(r[j]-l[j]+1)*h[j]);
		}
	}
	cout << ans;
}
signed main() {
	#define name 
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if (fopen(name".inp", "r")) {
		freopen(name".inp", "r", stdin);
		freopen(name".out", "w", stdout);
	}
	sub();
	return 0;
}
//honguwu

3. Bài tập áp dụng

4. 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