Giả sử chúng ta có một danh sách các số được gọi là lần đẩy và một danh sách các số khác được gọi là cửa sổ bật lên, chúng ta phải kiểm tra xem đây có phải là một chuỗi hợp lệ của các hành động đẩy và bật lên ngăn xếp hay không.
Vì vậy, nếu đầu vào giống như push =[1, 2, 5, 7, 9] pops =[2, 1, 9, 7, 5], thì đầu ra sẽ là True, vì chúng ta có thể push [1, 2] đầu tiên sau đó bật cả hai. Sau đó, đẩy [5, 7, 9] và bật tất cả chúng.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- s:=một ngăn xếp mới
- i:=0
- đối với mỗi lần cử đẩy, hãy thực hiện
- đẩy ele vào s
- trong khi kích thước của s> 0 và pops [i] là cùng một phần tử trên cùng của s, do
- xóa phần tử hàng đầu khỏi s
- i:=i + 1
- trả về true khi kích thước của s bằng 0, ngược lại là false
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
class Solution: def solve(self, pushes, pops): s = [] i = 0 for ele in pushes: s.append(ele) while len(s) > 0 and pops[i] == s[-1]: s.pop() i += 1 return len(s) == 0 ob = Solution() pushes = [1, 2, 5, 7, 9] pops = [2, 1, 9, 7, 5] print(ob.solve(pushes, pops))
Đầu vào
[1, 2, 5, 7, 9], [2, 1, 9, 7, 5]
Đầu ra
True