下面列出了java.util.Stack#pop ( ) 实例代码,或者点击链接到github查看源代码,也可以在右侧发表评论。
@Override
public EvalNode visitBetween(Context ctx, Stack<Expr> stack, BetweenPredicate between) throws TajoException {
stack.push(between);
EvalNode predicand = visit(ctx, stack, between.predicand());
EvalNode begin = visit(ctx, stack, between.begin());
EvalNode end = visit(ctx, stack, between.end());
stack.pop();
// implicit type conversion
DataType widestType = CatalogUtil.getWidestType(
convert(predicand.getValueType()).getDataType(),
convert(begin.getValueType()).getDataType(),
convert(end.getValueType()).getDataType());
BetweenPredicateEval betweenEval = new BetweenPredicateEval(
between.isNot(),
between.isSymmetric(),
predicand, begin, end);
betweenEval = (BetweenPredicateEval) convertType(ctx, betweenEval, TypeConverter.convert(widestType));
return betweenEval;
}
/**
* Visits blocks in dom-tree order, starting at the current node.
* The {@code parent} parameter of the Visitor.visitBlock callback
* is currently always set to null.
*
* @param v {@code non-null;} callback interface
*/
public void forEachBlockDepthFirstDom(SsaBasicBlock.Visitor v) {
BitSet visited = new BitSet(getBlocks().size());
Stack<SsaBasicBlock> stack = new Stack<SsaBasicBlock>();
stack.add(getEntryBlock());
while (stack.size() > 0) {
SsaBasicBlock cur = stack.pop();
ArrayList<SsaBasicBlock> curDomChildren = cur.getDomChildren();
if (!visited.get(cur.getIndex())) {
// We walk the tree this way for historical reasons...
for (int i = curDomChildren.size() - 1; i >= 0; i--) {
SsaBasicBlock child = curDomChildren.get(i);
stack.add(child);
}
visited.set(cur.getIndex());
v.visitBlock(cur, null);
}
}
}
private FocusedRange restoreSelectionAfterUndoRedo(DocOp transformedNonUndoable,
Stack<FocusedRange> selectionStack) {
if (selectionStack.isEmpty()) {
logger.log(Level.ERROR,
"SelectionStack empty! This probably shouldn't be reached, but we can live with it.");
return null;
}
FocusedRange selection = selectionStack.pop();
if (selection == UNKNOWN_SELECTION) {
logger.log(Level.TRACE, "unknown selection");
return null;
} else {
if (transformedNonUndoable != null) {
selection =
RangeHelper.applyModifier(transformedNonUndoable, selection);
}
selectionHelper.setSelectionRange(selection);
return selection;
}
}
/** 使用栈 */
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
} else {
if (stack.isEmpty()) {
return false;
}
char cStack = stack.pop(); // 先进后出,如果找到一个‘(’但是栈顶不为‘)’,则不可能匹配
boolean b1 = c == ')' && cStack != '(';
boolean b2 = c == ']' && cStack != '[';
boolean b3 = c == '}' && cStack != '{';
if (b1 || b2 || b3) {
return false;
}
}
}
return stack.isEmpty();
}
private void walk ( final Stack<DataSourceNode> stack, final DataSourceNode node )
{
if ( stack.contains ( node ) )
{
this.logStream.println ( "Loop found: " + StringHelper.join ( stack, " -> " ) );
// loop found
return;
}
stack.push ( node );
for ( final DataSourceNode ref : node.getReferences () )
{
walk ( stack, ref );
}
stack.pop ();
}
@Override
public EvalNode visitFuncCall(LogicalPlanner.PlanContext context, FunctionEval function, Stack<EvalNode> stack) {
stack.push(function);
for (int i = 0; i < function.getArgs().length; i++) {
if (function.getArgs()[i].getType() == EvalType.FIELD) {
FieldEval fieldEval = (FieldEval) function.getArgs()[i];
if (context.getQueryBlock().isConstReference(fieldEval.getName())) {
function.setArg(i, context.getQueryBlock().getConstByReference(fieldEval.getName()));
continue;
}
}
visit(context, function.getArgs()[i], stack);
}
stack.pop();
return function;
}
private void dfs(UnorderedGraph graph, int source, int index) {
Stack<Integer> elements = new Stack<Integer>();
elements.push(source);
while (!elements.isEmpty()) {
int element = elements.pop();
connectivityGroups[element] = index;
marked[element] = true;
Iterator<Integer> iterator = graph.adj(element).iterator();
// added
boolean isNotElement = element >= graph.verticesCount() / 2;
int elementIndex = isNotElement ? graph.verticesCount() - 1 - element : element;
solution[elementIndex] = !isNotElement;
// end added
while (iterator.hasNext()) {
int w = iterator.next();
if (!marked[w]) {
elements.push(w);
// added
if (connectivityGroups[graph.verticesCount() - 1 - w] == index) {
isSolutionExists = false;
return;
}
}
}
}
}
public int largestRectangleArea(int[] heights) {
int len = heights.length;
List<Integer> heightsArr = new ArrayList<>();
for (int i = 0; i < len; i++) {
heightsArr.add(heights[i]);
}
// 这里 -1 换成 0 也是可以的
heightsArr.add(-1);
int res = 0;
Stack<Integer> stack = new Stack<>();
// 注意这里是等于 i <= len;
for (int i = 0; i <= len; i++) {
// 严格小于的时候,才弹栈结算
while (!stack.isEmpty() && heightsArr.get(stack.peek()) > heightsArr.get(i)) {
int left = stack.pop();
// 这一步要小心,如果弹出以后,栈是空的,那说明,刚刚弹出的就是目前看到的所有高度里最小的
if (!stack.isEmpty()) {
res = Math.max(res, heightsArr.get(left) * (i - stack.peek() - 1));
} else {
res = Math.max(res, heightsArr.get(left) * i);
}
}
stack.push(i);
}
return res;
}
protected void transformSourceBlock(Block turningBlockSource, Block turningBlockFlowing){
if(FluidUtils.isSourceBlock(getWorld(), getX(), getY(), getZ())) {
getWorld().setBlock(getX(), getY(), getZ(), turningBlockSource);
onLiquidTransition(getX(), getY(), getZ());
} else {
Set<ChunkPosition> traversed = new HashSet<ChunkPosition>();
Stack<ChunkPosition> pending = new Stack<ChunkPosition>();
pending.push(new ChunkPosition(getX(), getY(), getZ()));
while(!pending.isEmpty()) {
ChunkPosition pos = pending.pop();
for(ForgeDirection d : ForgeDirection.VALID_DIRECTIONS) {
ChunkPosition newPos = new ChunkPosition(pos.chunkPosX + d.offsetX, pos.chunkPosY + d.offsetY, pos.chunkPosZ + d.offsetZ);
Block checkingBlock = getWorld().getBlock(newPos.chunkPosX, newPos.chunkPosY, newPos.chunkPosZ);
if((checkingBlock == getBlock() || getBlock() == Blocks.flowing_water && checkingBlock == Blocks.water || getBlock() == Blocks.flowing_lava && checkingBlock == Blocks.lava) && traversed.add(newPos)) {
if(FluidUtils.isSourceBlock(getWorld(), newPos.chunkPosX, newPos.chunkPosY, newPos.chunkPosZ)) {
getWorld().setBlock(newPos.chunkPosX, newPos.chunkPosY, newPos.chunkPosZ, turningBlockSource);
onLiquidTransition(newPos.chunkPosX, newPos.chunkPosY, newPos.chunkPosZ);
return;
} else {
getWorld().setBlock(newPos.chunkPosX, newPos.chunkPosY, newPos.chunkPosZ, turningBlockFlowing);
onLiquidTransition(newPos.chunkPosX, newPos.chunkPosY, newPos.chunkPosZ);
pending.push(newPos);
}
}
}
}
}
}
private static void parseProxy(Stack<String> args) {
int port = 55555;
String portStr = args.peek();
if (portStr != null && portStr.startsWith("-P")) {
args.pop();
try {
port = Integer.parseInt(portStr.substring(2));
} catch (NumberFormatException nex) {
System.err.println("Bad port number");
}
}
Main.startProxy(port);
}
@Override
public RESULT visitTableSubQuery(CONTEXT context, LogicalPlan plan, LogicalPlan.QueryBlock block,
TableSubQueryNode node, Stack<LogicalNode> stack) throws PlanningException {
stack.push(node);
LogicalPlan.QueryBlock childBlock = plan.getBlock(node.getSubQuery());
RESULT result = visit(context, plan, childBlock, childBlock.getRoot(), new Stack<LogicalNode>());
stack.pop();
return result;
}
public void postSearchComplete(PostSearchCompleteInterceptorChain chain,
DistinguishedName base, Int scope, Filter filter,
ArrayList<Attribute> attributes, Bool typesOnly,
LDAPSearchConstraints constraints) throws LDAPException {
Stack<JoinData> joinStack = (Stack<JoinData>) chain.getRequest().get(this.stackKey);
if (joinStack != null && joinStack.size() > 0 ) {
joinStack.pop();
}
}
/**
* Searches a collection of Strings for those which are within a given edit distance from a particular String.
*
* This version of fuzzy search uses a pre-computed map of transitions, and is the fastest method for max
* edit distances less than or equal 2. Greater max edit distances require huge amounts of memory and
* are not guaranteed to be faster than a non-automaton approach, so use in those cases is discouraged.
* @param maxEditDistance an int denoting the maximum amount of edit operations that can separate
* a String in the to-be-searched collection with the String of interest
* @param automatonString the String that all edit-distance calculations are to be carried out in relation to
* @param mdag an MDAG containing the set of Strings to be processed against {@code automatonString}
* @return a LinkedList containing all the Strings in {@code mdag} that are at most
* {@code maxEditDistance} away from {@code automatonString}
*/
public static LinkedList<String> tableFuzzySearch(int maxEditDistance, String automatonString, MDAG mdag)
{
//LinkedList which will contain Strings in mdag that are within maxEditDistance of automatonString
LinkedList<String> resultStringLinkedList = new LinkedList<String>();
//HashMap containing the transition relationships between the parametric states of an automaton with maxEditDistance
createParametricStateTransitionMap(maxEditDistance);
HashMap<ParametricState, HashMap<AugBitSet, ParametricState>> transitionHashMap = transitionHashMapContainerHashMap.get(maxEditDistance);
//Stack to store collections of objects which collectively represent steps in the search process
Stack<Object[]> processingStepStack = new Stack<Object[]>();
boolean mdagIsSimplified = mdag.getSourceNode().getClass().equals(SimpleMDAGNode.class);
SimpleMDAGNode[] simpleMDAGArray = mdag.getSimpleMDAGArray();
//Push onto processingStepStack the collection of objects which represent the start step of the search process
processingStepStack.push(createProcessingStepStackEntry("", mdag.getSourceNode(), initialState, new ParametricState(initialState)));
//Retrieve the set of characters composing the Strings in mdag
TreeSet<Character> charTreeSet = mdag.getTransitionLabelSet();
int charCount = charTreeSet.size();
/////
//Iterate through charTreeSet, inserting each char in to charArray
int counter = 0;
char[] charArray = new char[charCount];
for(Character c : charTreeSet) charArray[counter++] = c.charValue();
/////
//Transition through the MDAG and the automaton represented by transitionHashMap in-sync, adding to
//resultStringLinkedList the char sequences that lead to both an accept node (MDAG) and accept state (transition map)
while(!processingStepStack.isEmpty())
{
//Pop the processing step at the top of the stack and re-cast its contents
Object[] currentProcessingStepDataArray = processingStepStack.pop();
Object currentNodeObj = currentProcessingStepDataArray[1];
State currentState = (State)currentProcessingStepDataArray[2];
ParametricState currentParametricState = (ParametricState)currentProcessingStepDataArray[3];
/////
//Loop through the chars in charArray, using each to transition the node & state in the
//processing step at the top of the stack. If both the node and state have valid
//transitions on a particular char, push the resulting transition String, node,
//and State on the top of the stack
for(int i = 0; i < charCount; i++)
{
char currentChar = charArray[i];
//Execute a transition on the current MDAG node using currentChar
Object transitionNode = (mdagIsSimplified ? ((SimpleMDAGNode)currentNodeObj).transition(simpleMDAGArray, currentChar) : ((MDAGNode)currentNodeObj).transition(currentChar));
if(transitionNode != null)
{
//Get currentState's relevant subword (with respect to currentChar) and
//use it to get the parametric version of the transition's result State
AugBitSet rscv = currentState.getRelevantSubwordCharacteristicVector(maxEditDistance, automatonString, currentChar);
ParametricState transitionParametricState = transitionHashMap.get(currentParametricState).get(rscv);
/////
if(transitionParametricState != null)
{
//Use transitionParametricState to create the actual State that is the result of the transition
State transitionState = transitionParametricState.createActualState(currentState.getMinimalBoundary() + transitionParametricState.getTransitionBoundaryOffset());
String transitionPathString = (String)currentProcessingStepDataArray[0] + currentChar;
//Push the resulting processing step on to the top of processingStepStack
processingStepStack.push(createProcessingStepStackEntry(transitionPathString, transitionNode, transitionState, transitionParametricState));
//If both transitionNode and transitionState are "accepting", add the sequence of chars that lead to them to resultStringLinkedList
if(MDAG.isAcceptNode(transitionNode) && isAcceptState(transitionState, automatonString.length(), maxEditDistance))
resultStringLinkedList.add(transitionPathString);
}
}
}
/////
}
/////
return resultStringLinkedList;
}
HyperGraph convert(String inputStr) {
HyperGraph tree = null;
Stack<String> stack = new Stack<>();
for (int i = 0; i < inputStr.length(); i++) {
char curChar = inputStr.charAt(i);
if (curChar == ')' && inputStr.charAt(i - 1) != ' ') {// end of a rule
StringBuffer ruleString = new StringBuffer();
label:
while (stack.empty() == false) {
String cur = stack.pop();
switch (cur) {
case beginSymbol: // stop
// setup a node
// HGNode(int i, int j, int lhs, HashMap<Integer,DPState> dpStates, HyperEdge
// initHyperedge, double estTotalLogP)
// public HyperEdge(Rule rule, double bestDerivationLogP, Double transitionLogP,
// List<HGNode> antNodes, SourcePath srcPath)
// public Rule(int lhs, int[] sourceRhs, int[] targetRhs, float[]
// featureScores, int arity, int owner, float latticeCost, int ruleID)
stack.add(nodeSymbol);// TODO: should be lHS+id
break label;
case nodeSymbol:
break;
default:
ruleString.append(cur);
break;
}
}
} else if (curChar == '(' && inputStr.charAt(i + 1) != ' ') {// begin of a rule
stack.add(beginSymbol);
} else {
stack.add("" + curChar);
}
}
return tree;
}
/**
* Runs getvar on the inStack. The parameter is popped
* off the {@code inStack}, and the variable's value is
* pushed back to the top of {@code inStack}.
* @param inStack the jep stack
* @throws ParseException
*/
@SuppressWarnings("unchecked") //Uses JEP, which doesn't use generics
@Override
public void run(final Stack inStack) throws ParseException
{
// check the stack
checkStack(inStack);
// get the parameter from the stack
final Object param1;
Object param2 = null;
//
// have to do this in reverse order...this is a stack afterall
//
if (curNumberOfParameters == 1)
{
param1 = inStack.pop();
}
else if (curNumberOfParameters == 2)
{
param2 = inStack.pop();
param1 = inStack.pop();
if (!(param2 instanceof Double))
{
throw new ParseException("Invalid parameter type");
}
}
else
{
throw new ParseException("Invalid parameter count");
}
if (param1 instanceof String)
{
Float result = null;
if (parent instanceof PlayerCharacter)
{
final PlayerCharacter character = (PlayerCharacter) parent;
result = getVariableForCharacter(character, param1);
}
else if (parent instanceof Equipment)
{
boolean bPrimary = true;
if (param2 != null)
{
bPrimary = (((Double) param2).intValue() != 0);
}
result = ((Equipment) parent).getVariableValue((String) param1, "", bPrimary, null);
}
else if (parent instanceof VariableProcessorPC)
{
final VariableProcessorPC vpc = (VariableProcessorPC) parent;
// check to see if this is just a variable
result = vpc.lookupVariable((String) param1, variableSource, null);
if (result == null)
{
result = vpc.getVariableValue(null, (String) param1, variableSource, 0);
}
}
else if (parent instanceof VariableProcessorEq)
{
VariableProcessorEq veq = (VariableProcessorEq) parent;
result = veq.getVariableValue(null, (String) param1, variableSource, 0);
}
else if (parent == null)
{
Logging.errorPrint("Ignored request for var " + String.valueOf(param1) + " with no parent.");
}
if (result == null)
{
throw new ParseException("Error retreiving variable:" + param1);
}
inStack.push(result.doubleValue());
}
else
{
throw new ParseException("Invalid parameter type");
}
}
public static boolean migrate(String fromVersion, Object migrator, Object customData) {
Stack<Integer> versionParts = new Stack<Integer>();
for (String part: StringUtils.split(fromVersion, "."))
versionParts.push(Integer.valueOf(part));
boolean migrated = false;
Class<?> current = migrator.getClass();
while (current != null && current != Object.class) {
MigratorAnalyzeResult migratorAnalyzeResult = getMigratorAnalyzeResult(current);
int version;
if (!versionParts.empty())
version = versionParts.pop();
else
version = 0;
int size = migratorAnalyzeResult.getMigrateMethods().size();
int start;
if (version != 0) {
start = size;
for (int i=0; i<size; i++) {
Method method = migratorAnalyzeResult.getMigrateMethods().get(i);
if (method.getName().equals("migrate" + version)) {
start = i;
break;
}
}
if (start == size) {
throw new RuntimeException("Can not find migrate method (migrator: " + current.getName() + ", method: " + "migrate" + version + ")");
} else {
start++;
}
} else {
start = 0;
}
for (int i=start; i<size; i++) {
Method migrateMethod = migratorAnalyzeResult.getMigrateMethods().get(i);
int previousVersion;
if (i != 0) {
Method previousMigrateMethod =
migratorAnalyzeResult.getMigrateMethods().get(i-1);
previousVersion = migratorAnalyzeResult.getMigrateVersions()
.get(previousMigrateMethod.getName());
} else {
previousVersion = 0;
}
int currentVersion = migratorAnalyzeResult.getMigrateVersions()
.get(migrateMethod.getName());
Object[] params = new String[]{current.getName(),
String.valueOf(previousVersion),
String.valueOf(currentVersion)};
logger.debug("Migrating data (migrator: {}, from version: {}, " + "to version: {})", params);
try {
migrateMethod.invoke(migrator, customData, versionParts);
} catch (Exception e) {
throw ExceptionUtils.unchecked(e);
}
migrated = true;
}
current = current.getSuperclass();
}
return migrated;
}
/**
* Populate queue stats.
*
* @param cluster the cluster
* @return the list
* @throws IOException Signals that an I/O exception has occurred.
* @throws InterruptedException the interrupted exception
*/
public List<QueueStats> getQueueStats(String clusterName, RMCommunicator rmCommunicator) throws IOException, InterruptedException {
List<QueueStats> queueInformation = new ArrayList<QueueStats>();
QueueInfo queueInfo;
try {
queueInfo = rmCommunicator.getQueueInfo(ROOT);
Stack<QueueInfo> stack = new Stack<QueueInfo>();
stack.push(queueInfo);
QueueInfo temp;
List<QueueInfo> list = null;
while (!stack.isEmpty()){
temp = stack.pop();
YarnQueueStats yarnQueueStats = new YarnQueueStats();
if(!temp.getQueueName().equals(ROOT)){
yarnQueueStats.setQueueName(temp.getQueueName());
if (Constants.CLOUDERA.equals(FileUtil.getClusterInfoDetail(Constants.HADOOP_DISTRIBUTION))
|| Constants.MAPR.equals(FileUtil.getClusterInfoDetail(Constants.HADOOP_DISTRIBUTION))
|| Constants.EMRMAPR.equals(FileUtil.getClusterInfoDetail(Constants.HADOOP_DISTRIBUTION))){//mapr code changes
yarnQueueStats.setMaximumCapacity(temp.getCapacity()*100);
yarnQueueStats.setCapacity(temp.getCapacity()*100);
yarnQueueStats.setCurrentCapacity(temp.getCurrentCapacity()*100);
}else{
yarnQueueStats.setMaximumCapacity(temp.getMaximumCapacity()*100);
yarnQueueStats.setCapacity(temp.getCapacity()*100);
yarnQueueStats.setCurrentCapacity(temp.getCurrentCapacity()*100);
}
queueInformation.add(yarnQueueStats);
}
list = temp.getChildQueues();
if (list != null && !list.isEmpty()) {
Iterator<QueueInfo> it = list.iterator();
while (it.hasNext()) {
stack.push(it.next());
}
}
yarnQueueStats =null;
}
return queueInformation;
} catch (YarnException e) {
LOGGER.error(JumbuneRuntimeException.throwYarnException(e.getStackTrace()));
}
return queueInformation;
}
private static void compare(ModelNode node1, ModelNode node2, boolean ignoreUndefined, boolean ignoreType, Stack<String> stack) {
if (! ignoreType) {
Assert.assertEquals(getCompareStackAsString(stack) + " types", node1.getType(), node2.getType());
}
if (node1.getType() == ModelType.OBJECT) {
ModelNode model1 = ignoreUndefined ? trimUndefinedChildren(node1) : node1;
ModelNode model2 = ignoreUndefined ? trimUndefinedChildren(node2) : node2;
final Set<String> keys1 = new TreeSet<String>(model1.keys());
final Set<String> keys2 = new TreeSet<String>(model2.keys());
// compare string representations of the keys to help see the difference
if (!keys1.toString().equals(keys2.toString())){
//Just to make debugging easier
System.out.print("");
}
Assert.assertEquals(getCompareStackAsString(stack) + ": " + node1 + "\n" + node2, keys1.toString(), keys2.toString());
Assert.assertTrue(keys1.containsAll(keys2));
for (String key : keys1) {
final ModelNode child1 = model1.get(key);
Assert.assertTrue("Missing: " + key + "\n" + node1 + "\n" + node2, model2.has(key));
final ModelNode child2 = model2.get(key);
if (child1.isDefined()) {
if (!ignoreUndefined) {
Assert.assertTrue(getCompareStackAsString(stack) + " key=" + key + "\n with child1 \n" + child1.toString() + "\n has child2 not defined\n node2 is:\n" + node2.toString(), child2.isDefined());
}
stack.push(key + "/");
compare(child1, child2, ignoreUndefined, ignoreType, stack);
stack.pop();
} else if (!ignoreUndefined) {
Assert.assertFalse(getCompareStackAsString(stack) + " key=" + key + "\n with child1 undefined has child2 \n" + child2.asString(), child2.isDefined());
}
}
} else if (node1.getType() == ModelType.LIST) {
List<ModelNode> list1 = node1.asList();
List<ModelNode> list2 = node2.asList();
Assert.assertEquals(list1 + "\n" + list2, list1.size(), list2.size());
for (int i = 0; i < list1.size(); i++) {
stack.push(i + "/");
compare(list1.get(i), list2.get(i), ignoreUndefined, ignoreType, stack);
stack.pop();
}
} else if (node1.getType() == ModelType.PROPERTY) {
Property prop1 = node1.asProperty();
Property prop2 = node2.asProperty();
Assert.assertEquals(prop1 + "\n" + prop2, prop1.getName(), prop2.getName());
stack.push(prop1.getName() + "/");
compare(prop1.getValue(), prop2.getValue(), ignoreUndefined, ignoreType, stack);
stack.pop();
} else {
Assert.assertEquals(getCompareStackAsString(stack) +
"\n\"" + node1.asString() + "\"\n\"" + node2.asString() + "\"\n-----", node1.asString().trim(), node2.asString().trim());
}
}
private String searchNearestOpenedTag(int lastOffset) {
Stack<String> closeTagStack = new Stack<String>();
boolean hasSingleEndTag = false;
for (int i = lastOffset; i >= 0; i--) {
String currentChar = getText(i, i);
if (isCommentBlock(i)) {
continue;
}
if (">".equals(currentChar)) {
if (hasSingleEndTag) {
return null;
}
if (i > 0 && "/".equals(getText(i - 1, i - 1))) {
hasSingleEndTag = true;
i--;
}
continue;
}
if ("<".equals(currentChar)) {
if (hasSingleEndTag) {
hasSingleEndTag = false;
continue;
}
String nextChar = getText(i + 1, i + 1);
if ("/".equals(nextChar)) {
String searchTagName = searchTagName(i + 2, lastOffset);
if(!searchTagName.isEmpty()){
closeTagStack.push(searchTagName);
}
continue;
}
String currentTagName = searchTagName(i + 1, lastOffset);
if (closeTagStack.isEmpty()) {
return currentTagName.isEmpty()?null:currentTagName+">";
} else {
String pop = closeTagStack.pop();
if (!currentTagName.equals(pop)) {
return null;
}
}
}
}
return null;
}
/**
* Stack.
* Let's say we are now at temperatures[i], t[i]. We need to:
* 1. Update all t[j], j in [0..i-1], that t[j] < t[i].
* 2. t[j] has not been updated.
* How can we know t[j] has not been updated yet?
* We can remove t[j] from some data structure when it gets updated.
* How to avoid scanning through all values in the data structure we are to use?
* The data structure records insertion order. Queue or stack?
* If queue, first removed value is the largest. If stack, first removed value is the smallest.
* Since t[i] is looking for smaller values and will stop and larger or equal value, we should use stack.
* Note that temperatures can duplicate.
*/
public int[] dailyTemperatures(int[] temperatures) {
int[] result = new int[temperatures.length];
Stack<Integer> stack = new Stack<>(); // A stack of indices.
for (int i = 0; i < temperatures.length; i++) {
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
int index = stack.pop();
result[index] = i - index;
}
stack.push(i);
}
return result;
}