Editing Sliding range minimum query
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 31: | Line 31: | ||
We can now use a [[deque]] as our data structure, where most recently added elements are near the front and oldest elements near the back. When adding a new element on the right, first pop off all the larger elements from the front. When removing an old element from the left, simply pop it off the back. The element at the back will always be minimal. This gives the promised linear time bound without any precomputation. | We can now use a [[deque]] as our data structure, where most recently added elements are near the front and oldest elements near the back. When adding a new element on the right, first pop off all the larger elements from the front. When removing an old element from the left, simply pop it off the back. The element at the back will always be minimal. This gives the promised linear time bound without any precomputation. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |