Bài toán: Cho mảng nhị phân nums (1 = push, 0 = pop). Kiểm tra chuỗi thao tác có hợp lệ trên stack/queue không (không pop từ rỗng).
Thuật toán
Duyệt mảng, đếm push_count: gặp 1 thì ++, gặp 0 thì --. Nếu bao giờ push_count < 0 → invalid.
Triển khai Python
def solve(nums):
push_count = 0
for val in nums:
if val == 1:
push_count += 1
else:
push_count -= 1
if push_count < 0:
return False
return True
# Test
print(solve([1, 0, 1, 1, 0, 1])) # True: Push,Pop,Push,Push,Pop,Push
print(solve([0, 1, 1])) # False: Pop đầu tiên từ rỗng
print(solve([1, 1, 0, 0])) # True: Push,Push,Pop,Pop
Kết quả
True
Giải thích
- Logic giống kiểm tra ngoặc đúng: push = '(', pop = ')'.
- Áp dụng cho cả stack và queue vì cả hai đều yêu cầu không pop từ rỗng.
- Không cần mô phỏng cấu trúc dữ liệu thực, chỉ đếm số lượng.
- Độ phức tạp: O(n) thời gian, O(1) không gian.